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;

public class DEdu5 {
	public static void main(String[] args) throws IOException {
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		String[] split = f.readLine().split(" ");
		int n = Integer.parseInt(split[0]), k = Integer.parseInt(split[1]);
		int[] a = new int[n];
		split = f.readLine().split(" ");
		for(int i = 0; i < split.length; i++) {
			a[i] = Integer.parseInt(split[i]);
		}
		
		int l = 0, r = -1, c = 0;
		int len = 1, fL = 0, fR = 0;
		int[] freq = new int[1000001];
		
		for(int i = 0; i < n; i++) {
//			System.out.println("i: " + i);
			boolean runs = false;
			if(c < k) { //can add more distinct numbers
				runs = true;
				if(freq[a[i]] == 0) { //is a distinct number
					freq[a[i]]++;
					c++;
					if(r+1 < n) {
//						System.out.println("inc1");
						r++;
					}
				} else { //duplicate number
					freq[a[i]]++;
//					System.out.println("a[i]: " + a[i]);
					if(r+1 < n) {
//						System.out.println("inc2");
						r++;
					}
				}
			} 
			if(c == k || i == a.length-1){ //no more distinct numbers are available for use
				//count num of duplicates after last number
//				System.out.println("Reached k distinct C: " + c);
				
				while(r+1 < n && freq[a[r+1]] > 0) { 
//					System.out.println("Dup Running");
					freq[a[r+1]]++;
					i++;
					r++;
				}
//				System.out.println(l + "  " + r);
				int curLen = (r-l)+1;
//				System.out.println(curLen + "  " + len);
				if(curLen > len) {
					len = curLen;
					fL = l; fR = r;
				}
				freq[a[l]]--;
				if(freq[a[l]] == 0) c--;
//				System.out.println("Freq: " + freq[a[l]]);
				l++;
				if(!runs) i--;
			}
//			System.out.println("C: " + c);
//			System.out.println(l + " " + r);
//			System.out.println();
		}
		out.println((fL+1) + " " + (fR+1));
		out.close();
	}
}

/*
15 3
402220 282419 650495 930659 650495 889316 305186 305186 402220 889316 282419 305186 402220 650495 930659
*/