Sắp xếp bằng hoán đổi xa

Cho một hoán vị $p$ của các số nguyên từ $1$ đến $n$, trong đó $n$ là số chẵn.

Nhiệm vụ của bạn là sắp xếp hoán vị này theo thứ tự tăng dần. Để làm điều đó, bạn được thực hiện không quá $5·n$ thao tác, mỗi thao tác có dạng:

• Chọn hai chỉ số $i$ và $j$ thoả mãn $2·|i-j|\ge n$, rồi hoán đổi $p_i$ và $p_j$.

Bạn không cần cực tiểu hoá số thao tác, chỉ cần dùng không quá $5·n$ thao tác. Có thể chứng minh rằng với mọi hoán vị đầu vào luôn tồn tại một cách làm như vậy.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ ($2\le n\le 3·{10}^5$, $n$ chẵn) là độ dài hoán vị.
• Dòng thứ hai chứa $n$ số nguyên đôi một khác nhau $p_1,p_2,\dots ,p_n$ ($1\le p_i\le n$).

Dữ liệu ra

• Dòng đầu ghi số nguyên $m$ ($0\le m\le 5·n$) là số thao tác bạn thực hiện.
• $m$ dòng tiếp theo, dòng thứ $k$ ghi hai số nguyên $a_k,b_k$ ($1\le a_k,b_k\le n$, $2·|a_k-b_k|\ge n$) là hai chỉ số được hoán đổi ở thao tác thứ $k$.

Sau khi thực hiện lần lượt tất cả các thao tác, mảng phải trở thành $1,2,\dots ,n$. Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Ràng buộc

• $2\le n\le 3·{10}^5$, $n$ chẵn
• $p$ là một hoán vị của $1,2,\dots ,n$
• $0\le m\le 5·n$

Ví dụ