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.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;


public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader in  = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		
		String[]tok = in.readLine().split(" ");
		int N = Integer.parseInt(tok[0]);
		int K = Integer.parseInt(tok[1]);
		tok = in.readLine().split(" ");
		int[]a = new int[N];
		for (int i=0;i<N;i++) {
			a[i] = Integer.parseInt(tok[i]);
		}
		
		int start=0,end=0;
		int max = 1;
		int maxl = 0, maxr=0;
		Map<Integer, Integer> used = new HashMap<Integer, Integer>();
		used.put(a[0], 1);
		while (start<N) {			
			while (end<N-1 && used.size()<K) {	
				end++;
				Integer val = used.get(a[end]);
				if (val==null) val = 1;
				else val++;
				used.put(a[end], val);
			}
			while (end<N-1 && used.containsKey(a[end+1])) {
				end++;
				Integer val = used.get(a[end]);
				used.put(a[end], val+1);
			}
			
			if (end-start+1 > max) {
				max = end-start+1;
				maxl=start;
				maxr=end;
			}			
			Integer val = used.get(a[start]);
			if (val>1) used.put(a[start], val-1);
			else used.remove(a[start]);
			start++;
		}
		
		out.println((maxl+1) + " " + (maxr+1));
		
		in.close();
		out.close();
		
	}
}