Cho một dãy gồm ~n~ số nguyên dương ~a_1, a_2, a_3, \ldots, a_n~ là hoán vị của các số nguyên từ ~1~ đến ~n~. Sử dụng các thao tác lần lượt đổi chỗ hai số ở vị trí ~i~ và ~j~ bất kỳ, hãy sắp xếp dãy ban đầu thành dãy tăng dần.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, a_3, \ldots, a_n~ là hoán vị của các số nguyên từ ~1~ đến ~n~.

Output

• Dòng đầu tiên in ra số ~k~ (~0 \leq k \leq 2 \times 10^5~) - số lượng thao tác cần dùng.
• ~k~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~i~, ~j~ cách nhau một khoảng trắng (~1 \leq i, j \leq n~) thể hiện một thao tác đổi ~a_i~ và ~a_j~ cho nhau.

Có thể chứng minh được rằng luôn tồn tại cách sắp xếp thoả mãn không sử dụng quá ~2 \times 10^5~ thao tác.

Subtasks

• Subtask ~1~ (~10\%~): ~n = 3~.
• Subtask ~2~ (~20\%~): ~n \leq 100~.
• Subtask ~3~ (~30\%~): ~n \leq 10^4~.
• Subtask ~4~ (~40\%~): Không có ràng buộc gì thêm.

Sample Test

Input:

4
3 4 1 2

Output:

2
1 3
2 4