2077년에는 문제 출제가 간단해집니다. 로봇이 무작위 연산들을 설정하여 문제를 생성한 뒤 스스로 해결합니다. 출제자는 그 문제가 올바른지 여부만 확인하면 됩니다.
다음은 2077년에서 온 문제입니다:
순열 $p_1, p_2, \dots, p_n$이 주어지며, $n$이 짝수임이 보장됩니다. 오직 한 종류의 연산만 사용하여 이 순열을 정렬하고자 합니다:
FakeSort(l,r): $r - l + 1$이 짝수임을 보장해야 합니다. $k = r - l + 1$이라 할 때, 연속 부분 수열 $p_l, p_{l+1}, \dots, p_r$에서 가장 큰 $k/2$개의 원소와 가장 작은 $k/2$개의 원소가 각각 독립적으로 정렬됩니다. 즉, 가장 큰 $k/2$개의 수들의 인덱스를 $L_1, L_2, \dots, L_{k/2}$라 하고, 가장 작은 $k/2$개의 수들의 인덱스를 $S_1, S_2, \dots, S_{k/2}$라 합시다. 먼저 인덱스 $L_1 \sim L_{k/2}$에 있는 수들을 정렬한 다음, 인덱스 $S_1 \sim S_{k/2}$에 있는 수들을 정렬합니다.
구체적인 예시는 다음과 같습니다. 순열이 $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$이라고 가정합시다. FakeSort(2,7)을 호출하면:
- $k = r - l + 1 = 6$입니다. 연속 부분 수열 $p_l, p_{l+1}, \dots, p_r$은 $\{5, 7, 1, 8, 6, 4\}$이며, 이 수열에서 가장 큰 $3$개의 수와 가장 작은 $3$개의 수를 각각 독립적으로 정렬합니다.
- $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; 가장 큰 $3$개의 수가 굵게 표시되어 있습니다. 정렬 후에는 $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$이 됩니다.
- $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; 가장 작은 $3$개의 수가 굵게 표시되어 있습니다. 정렬 후에는 $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$이 됩니다.
따라서 $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$은 FakeSort(2,7) 이후에 $\{2, 1, 6, 4, 7, 8, 5, 3\}$이 됩니다.
$114$번 이하의 연산을 사용하여 순열을 정렬하거나 불가능하다고 판단하세요. 만약 어떤 순열을 이 연산으로 정렬할 수 있다면, $114$번 이하의 연산만 사용하는 방법이 존재함을 증명할 수 있습니다.
입력
입력은 여러 개의 테스트케이스로 구성됩니다. 첫째 줄에 테스트케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 10^3$)가 주어집니다.
각 테스트케이스의 첫째 줄에는 순열의 길이를 나타내는 짝수 정수 $n$ ($4 \le n \le 10^5$)이 주어집니다.
둘째 줄에는 정렬해야 하는 순열을 나타내는 $n$개의 정수 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)이 주어집니다. $p$가 순열임이 보장됩니다.
모든 테스트케이스에 걸쳐 $n$의 합은 $2 \times 10^5$을 넘지 않음이 보장됩니다.
출력
각 테스트케이스마다 순열을 정렬하는 것이 불가능하다면 $-1$을 출력합니다.
그렇지 않다면 사용한 연산의 횟수를 나타내는 정수 $k$ ($0 \le k \le 114$)를 출력합니다.
그다음 $k$개의 줄에는 각 줄마다 FakeSort(l,r)을 수행함을 나타내는 $l, r$ ($1 \le l \le r \le n$, $r - l + 1$은 짝수)을 출력합니다.
예제
예제 입력 1
3 4 2 1 4 3 6 3 6 5 1 2 4 8 3 2 1 7 5 4 6 8
예제 출력 1
1 1 4 -1 2 4 7 1 6