32274번 - 수열 탈집중화 스페셜 저지

문제

$N$개의 수로 이루어진 수열 $A_1, A_2, \ldots, A_N$에서, 다음과 같은 두 가지 연산을 원하는 횟수만큼 시행할 수 있다.

• 1ドル$ $i$ $j$: $A_i, A_{i+1}, \ldots , A_j$ 을 모두 $\min(A_i, A_{i+1}, \ldots, A_j)$ 으로 치환한다.
• 2ドル$ $i$ $j$: $A_i, A_{i+1}, \ldots , A_j$ 을 모두 $\max(A_i, A_{i+1}, \ldots, A_j)$ 으로 치환한다.

예를 들어, $N=5$이고 $A_1, A_2, A_3, A_4, A_5$가 1,ドル 3, 5, 2, 4$ 였다면, 연산 2ドル$ 2ドル$ 3ドル$ 시행 후에는 1,ドル 5, 5, 2, 4$ 가 되고, 그 뒤에 연산 1ドル$ 3ドル$ 4ドル$ 를 시행하면 1,ドル 5, 2, 2, 4$가 된다.

당신의 목표는 $A_1, A_2, \ldots , A_N$이 최대한 한 곳에 집중되어있지 않도록 하는 것이다. 수열의 집중되어있지 않은 정도는 $\sum_{1 \le i, j \le N} (A_i-A_j)^2$로 정의된다. 이 값을 최대화하는 것이 목적이다.

주어진 수열 $A_1, A_2, \ldots , A_N$에 대해, 연산을 여러 번 시행하여 $\sum_{1 \le i, j \le N} (A_i-A_j)^2$ 의 값을 가능한 한 최대화 하는 방법 중 연산을 최소 횟수로 시행하는 방법을 찾아 출력하라. 최소 횟수의 방법이 여러가지라면 그 중 아무 것이나 출력하라.

입력

첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 $T$ 가 주어지고,

이후 차례로 $T$ 개의 테스트 케이스가 주어진다. (1ドル \le T \le 3,508円$)

각 테스트 케이스의 첫 줄에는 정수 $N$이 주어진다 (1ドル \le N \le 50,000円$).

다음 줄에는 $N$개의 정수 $A_1, A_2, \ldots, A_N$가 공백으로 구분되어 주어진다. (1ドル \le A_i \le 10^9$)

모든 테스트 케이스에서 $N$의 합은 2ドル,000円,000円$ 을 넘지 않는다.

출력

각 테스트 케이스마다 첫 줄에는 “Case #$C$”를 출력하여야 한다. 이때 $C$는 테스트 케이스의 번호이다.

다음 줄에는 최소 시행 횟수 $K$을 출력한다.

다음 $K$개의 줄에는 연산들을 시행한 순서대로 출력한다.

각 줄에는 시행 연산을 나타내는 세 수 $op, i, j$ 를 공백을 사이에 두고 출력한다. (1ドル \le op \le 2, 1 \le i \le j \le N$)

제한

힌트