34194번 - Permutation Swap 스페셜 저지

문제

길이가 $N$인 순열 $P_1, P_2, \cdots, P_N$이 주어진다. 길이가 $N$인 순열은 1ドル$ 이상 $N$ 이하의 모든 정수를 정확히 한 번씩 포함하는 수열이다.

아래와 같은 연산을 최대 한 번 수행할 수 있다.

• 1ドル \leq i < j \leq N$을 고른 뒤 $P_i, P_j$의 위치를 서로 바꾼다.

연산을 수행한 뒤 얻은 순열 $P_1', P_2', \cdots, P_N'$에서 1ドル \leq i < N$이면서 $P'_i < P'_{i+1}$인 인접한 증가 쌍 $(P'_i, P'_{i+1})$의 개수를 최대화하고자 한다.

인접한 증가 쌍의 개수가 최대화되는 연산 방법을 구해보자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T \le 100,000円)$

테스트 케이스의 첫 번째 줄에는 순열의 길이를 나타내는 정수 $N$이 주어진다. $(2 \leq N \leq 200,000円)$

테스트 케이스의 두 번째 줄에는 순열 $P_1, P_2, \cdots, P_N$이 공백으로 구분되어 주어진다. $(1 \leq P_i \leq N)$

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

출력

각 테스트 케이스에 대해, 인접한 증가 쌍의 개수가 최대화되는 연산 방법을 한 줄에 출력한다.

• 연산을 수행하지 않는 것이 최적이라면 $-1$을 출력한다.
• 연산을 수행한다면 선택한 두 위치 $i, j$를 공백으로 구분하여 출력한다. $(1 \le i < j \le N)$

가능한 정답이 여러 개라면, 그중 아무거나 하나 출력한다.

제한

노트