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.util.*;
import java.io.*;
public class B{
	static int sz = (int)(1e6)+5;
	public static void main(String[] args)
	{
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		int n = fs.nextInt(); int k = fs.nextInt();
		int[] count = new int[sz];
		int[] arr = fs.readArray(n);
		int cur = 0;
		int max = 0;
		int l = -1; int r = -1;
		int j = 0;
		me:for(int i=0;i<n;i++)
		{
			if(i != 0)
			{
				count[arr[i-1]]--;
				if(count[arr[i-1]] == 0)
				{
					cur -= 1;
				}
			}
			for(;j<n;j++)
			{
				if(cur>k)
				{
					continue me;
				}
				if(count[arr[j]] == 0)
				{
					count[arr[j]]++;
					cur++;
				}
				else count[arr[j]]++;
				if((j-i+1)>max && cur<=k)
				{
					max = (j-i+1);
					l = (i+1);
					r = (j+1);
				}
			}
		}
		out.println(l+" "+r);
		out.close();
	}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	public static int[] sort(int[] arr)
	{
		List<Integer> temp = new ArrayList();
		for(int i:arr)temp.add(i);
		Collections.sort(temp);
		int start = 0;
		for(int i:temp)arr[start++]=i;
		return arr;
	}
	public static String rev(String str)
	{
		char[] arr = str.toCharArray();
		char[] ret = new char[arr.length];
		int start = arr.length-1;
		for(char i:arr)ret[start--] = i;
		String ret1 = "";
		for(char ch:ret)ret1+=ch;
		return ret1;
	}
}