Problem: The array a with n integers is given. Let's call the sequence of one or more consecutive elements in a segment. Also let's call the segment k-good if it contains no more than k different values.

Find any longest k-good segment.

As the input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input

The first line contains two integers n, k (1 ≤ k ≤ n ≤ 5·105) — the number of elements in a and the parameter k.

The second line contains n integers ai (0 ≤ ai ≤ 106) — the elements of the array a.

Output

Print two integers l, r (1 ≤ l ≤ r ≤ n) — the index of the left and the index of the right ends of some k-good longest segment. If there are several longest segments you can print any of them. The elements in a are numbered from 1 to n from left to right.

Examples

Input

5 5
1 2 3 4 5


Output

1 5


Input

9 3
6 5 1 2 3 2 1 4 5


Output

3 7


Input

3 1
1 2 3


Output

1 1

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

public class C {

	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

		String line = r.readLine();
		int n = Integer.parseInt(line);
		line = r.readLine();
		String[] split = line.split(" ");

		HashMap<Integer, Integer> map = new HashMap<>();
		int row[] = new int[n];
		int z = 0, m = 0, i = 0;
		for (String s : split) {
			z = Integer.parseInt(s);
			if (map.containsKey(z))
				row[i] = map.get(z);
			else {
				map.put(z, m);
				row[i] = m++;
			}
			i++;
		}

		int last[] = new int[m];
		int best[] = new int[n];
		int path[] = new int[n];

		last[row[0]] = 1;
		path[0] = -1;
		for (i = 1; i < n; i++) {
			int l = last[row[i]];
			if (l == 0) {
				best[i] = best[i - 1];
				path[i] = path[i - 1];
			} else {
				int x = l > 1 ? best[l - 2] + 1 : 1;
				if (best[i - 1] > x) {
					best[i] = best[i - 1];
					path[i] = path[i - 1];
				} else {
					best[i] = x;
					path[i] = l - 1;
				}
			}
			last[row[i]] = i + 1;
		}

		if (best[n - 1] == 0)
			System.out.println(-1);
		else {
			System.out.println(best[n - 1]);
			printOutput(n - 1, path);
		}
	}

	private static void printOutput(int i, int[] path) {
		if (path[i] == 0 || path[path[i]-1] == -1)
			System.out.println("1 " + (i + 1));
		else {
			printOutput(path[i] - 1, path);
			System.out.println((path[i]+1) + " " + (i + 1));
		}
	}

}