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.awt.Point;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
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 {
		File inputFile = new File("entradaC");
		if (inputFile.exists())
			System.setIn(new FileInputStream(inputFile));
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String line;
		StringBuilder out = new StringBuilder();
		while ((line = in.readLine()) != null) {
			int n = Integer.parseInt(line);
			long[] v = readLongs(in.readLine());
			HashMap<Long, Integer> map = new HashMap<>();
			int last = -1, pos = 0;
			ArrayList<Point> ans = new ArrayList<>();
			for (int i = 0; i < v.length; i++) {
				if (map.containsKey(v[i])) {
					pos = map.get(v[i]);
					if (pos <= last)
						map.put(v[i], i);
					else {
						ans.add(new Point(last + 2, i + 1));
						last = i;
					}

				} else
					map.put(v[i], i);
			}
			if (ans.isEmpty())
				out.append("-1\n");
			else {
				out.append(ans.size() + "\n");
				Point c;
				for (int i = 0; i < ans.size() - 1; i++) {
					c = ans.get(i);
					out.append(c.x + " " + c.y + "\n");
				}
				c = ans.get(ans.size() - 1);
				out.append(c.x + " " + n + "\n");
			}
		}
		System.out.print(out);
	}

	public static int[] readInts(String line) {
		String[] w = line.trim().split("\\s+");
		int[] a = new int[w.length];
		for (int i = 0; i < a.length; i++)
			a[i] = Integer.parseInt(w[i]);
		return a;
	}

	public static long[] readLongs(String line) {
		String[] w = line.trim().split("\\s+");
		long[] a = new long[w.length];
		for (int i = 0; i < a.length; i++)
			a[i] = Long.parseLong(w[i]);
		return a;
	}
}