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:
/*
 * Code Author: Jayesh Udhani
 * Institute  : DA-IICT 
 * 3rd year BTech ICT Student
 */

import java.io.*;
import java.util.*;
public class CFEDU5D
{
	private static int[] nextIntArray(InputReader in,int n)	
	{
		int[] a=new int[n];
		for(int i=0;i<n;i++)
			a[i]=in.nextInt();
		return a;
	}
	public static void main(String args[])
	{
		InputReader in = new InputReader(System.in);
		OutputStream outputStream = System.out;
		PrintWriter out = new PrintWriter(outputStream);
		/*------------------------------My Code starts here------------------------------*/
		int n=in.nextInt(),k=in.nextInt(),max=Integer.MIN_VALUE,l=0,r=0,x=-1,y=-1;
		int[] a=nextIntArray(in, n);
		Map<Integer,Integer> hm=new HashMap<>();
		for(;r<n;r++)
		{
			if(hm.containsKey(a[r]))
				hm.put(a[r], hm.get(a[r])+1);
			else
				hm.put(a[r], 1);
			if(l<n && hm.size()>k)
			{
				while(hm.size()>k)
				{
					if(hm.get(a[l])==1)
						hm.remove(a[l]);
					else 
						hm.put(a[l], hm.get(a[l])-1);
					l++;
				}
			}
			if(r-l+1>max)
			{
				max=r-l+1;
				x=l;
				y=r;
			}
		}
		x++;
		y++;
		out.println(x+" "+y);
		out.close();
		/*------------------------------The End------------------------------------------*/
	}
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream inputstream) {
			reader = new BufferedReader(new InputStreamReader(inputstream));
			tokenizer = null;
		}

		public String nextLine(){
			String fullLine=null;
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					fullLine=reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				return fullLine;
			}
			return fullLine;
		}
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}