34185번 - SWAP-C Sort 스페셜 저지

문제

길이 $n$의 순열 $P = P_1, P_2, \cdots, P_n$이 주어진다. 순열 $P$에는 1ドル$ 이상 $n$ 이하의 정수가 정확히 한 번씩 등장한다.

1ドル \le i < j \le n$인 모든 쌍 $(i, j)$에 대해 $P_i$와 $P_j$를 교환하는 동작을 정확히 한 번씩, 총 $\frac{n(n-1)}{2}$번의 동작을 수행하여 $P$를 정렬할 수 있는지 판별하고, 가능하다면 그러한 방법을 아무거나 하나 출력하시오.

입력

첫 번째 줄에는 순열의 길이 $n$이 주어진다. (2ドル \le n \le 1000$)

두 번째 줄에는 $P_1, P_2, \cdots, P_n$의 값이 순서대로 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 문제의 조건에 맞게 $P$를 정렬할 수 있으면 1, 아니면 0을 출력한다.

정렬할 수 있는 경우, 그러한 $\frac{n(n-1)}{2}$번의 동작을 순서대로 한 줄에 하나씩 출력한다. $i$번째 원소와 $j$번째 원소를 교환할 때, $i$와 $j$를 공백으로 구분하여 출력한다. $i$와 $j$의 대소 관계는 상관 없다.

제한

힌트