• Cho một mảng chứa một hoán vị của các số nguyên \(1,2,...,n\). Hãy sắp xếp mảng theo thứ tự tăng dần bằng cách đảo ngược các mảng con. Bạn có thể in ra bất kỳ lời giải nào có nhiều nhất \(n\) lần đảo.

Input

• Dòng đầu tiên nhập số nguyên \(n\): kích thước của mảng. Các phần tử của mảng được đánh số \(1,2,…, n\).
• Dòng tiếp theo có n số nguyên \(x_1, x_2,…, x_n\): phần tử của mảng

Output

• Dòng đầu in số nguyên \(k\): số lần đảo.
• \(k\) dòng tiếp theo mô tả cho mỗi lần đảo. Mỗi dòng có hai số nguyên \(a\) và \(b\): đảo ngược mảng con từ \(a\) đến \(b\).

Constraints

• \(1\leq n \leq 2 ⋅ 10^5\)

Example

Sample input:

4  
2 3 1 4

2  
1 3  
2 3