Pha Lê

Dạng bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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 ban đầu là độ đa dạng nhỏ nhất của các chuỗi 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.

Dữ liệu vào

Dòng đầu chứa số nguyên dương \(n (n ≤ 5 × 10^{5})\) xác định số lượng hạt trong chuỗi ban đầu;
Dòng thứ hai chứa n số nguyên dương \(a1, a2, …, an\) \((1 ≤ i ≤ n)\) xác định loại của các hạt trong chuỗi theo thứ tự.

Dữ liệu ra

-Dòng đầu chứa số nguyên dương \(k\) là số lượng cách cắt chuỗi ban đầu thành các chuỗi con cùng độ dài;

\(k\) dòng tiếp theo, dòng thứ \(i\) \((1 ≤ i ≤ k)\) chứa 2 số nguyên dương \(xi\), \(yi\) với \(xi\) là kích thước các chuỗi con mới theo cách cắt thứ \(i\) và \(yi\) 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 của kích thước chuỗi hạt con.