수열 탈집중화

$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$)