Pha lê Swarovski được dùng làm đồ trang sức vô cùng đẹp và vô cùng giá trị. Các hạt pha lê gồm rất nhiều loại khác nhau, mỗi loại được ký hiệu đại diện bởi một số nguyên dương không vượt quá ~10^9~. Trong một lần thám hiểm vùng rừng rậm Amazon, đoàn thám hiểm đã tìm thấy một chuỗi rất dài gồm ~n~ hạt pha lê được gắn liên tiếp nhau. Trước khi đưa về nghiên cứu, người ta quyết định cắt chuỗi hạt tìm thấy thành các chuỗi con gồm các hạt liên tiếp có cùng độ dài. Khi đó độ đa dạng của từng chuỗi hạt là số lượng loại hạt khác nhau tồn tại trong chuỗi hạt đó. Độ đa dạng trong một cách cắt chuỗi hạt ban đầu là độ đa dạng nhỏ nhất của các chuỗi hạt tạo thành.

Yêu cầu: Hãy xác định số lượng cách cắt chuỗi hạt, độ dài chuỗi hạt con và độ đa dạng của từng cách cắt tương ứng.

Input

• Dòng đầu chứa số nguyên dương ~n~ (~n \le 5 \times 10^5~) xác định số lượng hạt trong chuỗi hạt ban đầu.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le n~) xác định loại của các hạt trong chuỗi hạt ban đầu.

Output

• Dòng đầu chứa số nguyên dương ~k~ - số lượng cách cắt chuỗi hạt đầu thành các chuỗi con cùng độ dài.
• ~k~ dòng tiếp theo, dòng thứ ~i~ (~1 \le i \le k~) chứa hai số nguyên dương ~x_i~ và ~y_i~ là độ dài của từng cách cắt và ~y_i~ là độ đa dạng của cách cắt tìm được. Các cách cắt liệt kê theo thứ tự tăng dần của kích thước chuỗi hạt con.

Sample Input 1

6
1 2 2 4 3 3

Sample Output 1

4
1 1
2 1
3 2
6 4

Subtasks