Sắp xếp

Hôm nay Tí và Tèo chơi một trò chơi về số nguyên. Tí có một dãy số nguyên không âm $a_1,a_2,\dots ,a_n$. Tí cần sắp xếp dãy theo thứ tự không giảm chỉ bằng thao tác sau: chọn hai chỉ số $i,j$ $(1\le i<j\le n)$, sau đó đảo ngược đoạn từ $i$ đến $j$ (tức là đoạn $a_i,a_{i+1},\dots ,a_j$ trở thành $a_j,a_{j-1},\dots ,a_i$).

Tí muốn Tèo sắp xếp dãy $a_1,a_2,\dots ,a_n$ theo yêu cầu trên với số thao tác không vượt quá $2·n$. Tèo chưa biết cách thực hiện nên mong muốn bạn giúp đỡ.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$.
• Dòng thứ hai gồm $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$ $(a_i\le {10}^9)$.

Dữ liệu ra

• Dòng đầu tiên ghi số nguyên $s$ $(0\le s\le 2·n)$ là số thao tác cần thực hiện.
• $s$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $i,j$ $(1\le i<j\le n)$ mô tả một thao tác đảo ngược đoạn từ $i$ đến $j$. Các thao tác được thực hiện lần lượt theo thứ tự in ra.

Sau khi thực hiện $s$ thao tác, dãy phải được sắp xếp theo thứ tự không giảm. Không cần số thao tác ít nhất; nếu có nhiều cách, in ra một cách bất kỳ.

Ràng buộc

• $1\le n\le {10}^5$.
• $0\le a_i\le {10}^9$.

Subtasks

• Subtask 1 ($40\%$ số điểm): $n\le {10}^3$.
• Subtask 2 ($60\%$ số điểm): không có ràng buộc gì thêm ($n\le {10}^5$).

Ví dụ