Pythagoras cho rằng toán học là nền tảng của thế giới. Ngày nay, các nhà sinh học cũng nghiên cứu những tính chất toán học của các dãy sinh học.

Trong bài này, một dãy sinh học gồm \(M\) số nguyên và thỏa mãn các điều kiện sau:

• Chứa mỗi số trong các số \(0,1,\ldots,M-1\) đúng một lần.
• Bắt đầu bằng \(0\) và kết thúc bằng \(M-1\).
• Không có hai phần tử liên tiếp mang giá trị \(E,E+1\) theo đúng thứ tự đó.

Một đoạn gồm các phần tử ở những vị trí liên tiếp của dãy. Một đoạn được gọi là đoạn có khung nếu phần tử đầu là phần tử nhỏ nhất, phần tử cuối là phần tử lớn nhất và khác phần tử đầu, đồng thời đoạn chứa tất cả các số nguyên từ giá trị phần tử đầu đến giá trị phần tử cuối.

Một đoạn có khung được gọi là một empodio nếu bên trong nó không có đoạn có khung nào ngắn hơn. Từ empodia là dạng số nhiều của empodio.

Ví dụ, xét dãy \((0,3,5,4,6,2,1,7)\). Cả dãy là một đoạn có khung, nhưng không phải empodio vì nó chứa đoạn có khung \((3,5,4,6)\). Đoạn \((3,5,4,6)\) không chứa đoạn có khung nào ngắn hơn, nên đây là một empodio; nó cũng là empodio duy nhất của dãy này.

Hãy tìm tất cả các empodia của dãy sinh học được cho.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(M\), số phần tử của dãy.
• \(M\) dòng tiếp theo, mỗi dòng chứa một số nguyên, lần lượt là các phần tử của dãy theo thứ tự.

Dữ liệu ra

• Dòng đầu chứa số nguyên \(H\), số empodia của dãy.
• \(H\) dòng tiếp theo mô tả tất cả các empodia theo thứ tự tăng dần của vị trí bắt đầu. Mỗi dòng chứa hai số nguyên \(A\) và \(B\): vị trí phần tử đầu và phần tử cuối của empodio. Các vị trí được đánh số từ \(1\).

Ràng buộc

Có một bộ kiểm thử với \(1000000\le M\le 1100000\). Trong tất cả các bộ kiểm thử còn lại, \(1\le M\le 60000\).

Phân nhóm

Có 20 bộ kiểm thử, mỗi bộ có số điểm tối đa là 5. Trong 50% số bộ kiểm thử, \(M\le 2600\).

Ví dụ

8
0
3
5
4
6
2
1
7

1
2 5