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.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;

public class L {
	static int MAX_SIZE = 1000001;

	public static void main(String[] args) throws IOException {
		File inputFile = new File("entradaL");
		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[] nk = readInts(line);
			int n = nk[0], k = nk[1];
			int[] count = new int[MAX_SIZE];
			int[] last = new int[MAX_SIZE];
			int front = 0, tail = 0, dif = 0, s = 0, e = 0;
			int[] v = readInts(in.readLine());
			while (front < n) {
				// Adding
				while (dif <= k && front < n) {
					if (count[v[front]] == 0) {
						if (dif == k)
							break;
						dif++;
					}
					count[v[front]]++;
					last[v[front]] = front;
					if (front - tail > e - s) {
						e = front;
						s = tail;
					}
					front++;
				}
				// Removing
				if (front >= n) {
					continue;
				} else {
					while (tail < front) {
						count[v[tail]]--;
						if (count[v[tail++]] == 0) {
							dif--;
							break;
						}
					}
				}
			}
			out.append(++s + " " + ++e + "\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;
	}
}