Adam is shopping for his girlfriend's birthday. His girlfriend loves pearls, but as he has to attend CODEBLAZE , he gives the responsibility to you.

There are n pearls in a row. Let's number them with integers from 1 to n from the left to the right. The pearl number i has the type ai.

Let's call a sequence of consecutive pearls a segment. Let's call a segment good if it contains two pearls of the same type.

Split the row of the pearls to the maximal number of good segments.

INPUT

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of pearls in a row.

The second line contains n integers ai (1 ≤ ai ≤ 10^9) – the type of the i-th pearl.

OUTPUT

On the first line print integer k — the maximal number of segments in a partition of the row.

Each of the next k lines should contain two integers lj, rj (1 ≤ lj ≤ rj ≤ n) — the number of the leftmost and the rightmost pearls in the j-th segment.

If there are no correct partitions of the row print the number "-1".