Ngọc trai trên hàng

Có $n$ viên ngọc trai xếp thành một hàng, đánh số từ $1$ đến $n$ từ trái sang phải. Viên ngọc thứ $i$ có loại $a_i$.

Một đoạn là một dãy các viên ngọc liên tiếp. Một đoạn được gọi là tốt nếu trong đoạn đó có ít nhất hai viên ngọc cùng loại.

Hãy chia hàng ngọc trai thành số lượng đoạn tốt nhiều nhất có thể. Mỗi viên ngọc phải thuộc đúng một đoạn của cách chia.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$: số viên ngọc trai.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$: loại của từng viên ngọc.

Dữ liệu ra

• Nếu không tồn tại cách chia hợp lệ, in ra một số $-1$.
• Ngược lại, dòng đầu in số nguyên $k$: số đoạn nhiều nhất. Mỗi dòng trong $k$ dòng tiếp theo in hai số nguyên $l_j,r_j$ ($1\le l_j\le r_j\le n$): chỉ số viên ngọc trái nhất và phải nhất của đoạn thứ $j$.

Cách chia phải hợp lệ: mỗi viên ngọc thuộc đúng một đoạn và mọi đoạn đều là đoạn tốt. Nếu có nhiều đáp án tối ưu, in ra một đáp án bất kỳ. Các đoạn có thể được in theo thứ tự bất kỳ.

Ràng buộc

• $1\le n\le 3·{10}^5$
• $1\le a_i\le {10}^9$

Ví dụ