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.*;
import static java.lang.Math.*;


public class cf2 implements Runnable {   
	
	long gcd(long a, long b) 
	{ 
	    if (a == 0) 
	        return b; 
	    return gcd(b % a, a); 
	} 

   long power(long x, long y, long p)
    {
       
        long res = 1;     
   
        x=x % p; 
     
        while (y > 0)
        {
            
            if((y & 1)==1)
                res = ((res%p) * (x%p))% p;
     
            y =y >> 1; 
            x =((x%p)*(x%p))%p; 
        }
        return res;
    }
	
  
	public void run() {
		
		InputReader in = new InputReader(System.in);
		PrintWriter w = new PrintWriter(System.out);
		
		int n=in.nextInt();
		int k=in.nextInt();
		
		int[] a=new int[n+1];
	
		
		int cnt=0;
		
		ArrayList<Integer> l=new ArrayList<>();
		ArrayList<Integer> r=new ArrayList<>();
		
		HashMap<Integer,Integer> hm=new HashMap<>();
		
		int max=0;
		
		for(int i=1;i<=n;i++)
		{
			a[i]=in.nextInt();
					
		}
		
		int j=1;
		for(int i=1;i<=n;)
		{
			if(i>n || j>n)
				break;
			
			//w.println(" i:"+i+" j:"+j+" 5 cnt: "+hm.get(a[2]));
			
				if(i==1 && j==1)
				{
					hm.put(a[i], 1);
				}
				cnt=hm.size();
				
			//	w.println("i: "+i+" j: "+j+" cnt: "+cnt);
				
				if(cnt==k)
				{
					l.add(i);
					r.add(j);
					j++;
					if(i>n || j>n)
						break;
					if(!hm.containsKey(a[j]))
					{
						hm.put(a[j], 1);
					}
					else
					{
						hm.put(a[j], hm.get(a[j])+1);
					}
				}
				else if(cnt<k)
				{
					l.add(i);
					r.add(j);
					j++;
					
					if(i>n || j>n)
						break;
					if(!hm.containsKey(a[j]))
					{
						hm.put(a[j], 1);
					}
					else
					{
						hm.put(a[j], hm.get(a[j])+1);
					}
					
				   // w.println("j++: "+a[j]+" "+hm.get(a[j]));
					
				}
				
				else if(cnt>k)
				{
					//w.println("reduce cnt: "+a[i]+" hmget: "+hm.get(a[i]));
					hm.put(a[i], hm.get(a[i])-1);
					if(hm.get(a[i])==0)
					{
						hm.remove(a[i]);
						//w.println("removed: "+a[i]);
					}
					i++;
					if(i>n || j>n)
						break;
					
					
				/*	if(!hm.containsKey(a[i]))
					{
						hm.put(a[i], 1);
					}
					else
					{
						hm.put(a[i], hm.get(a[i])+1);
					}
					*/
				    
					
				}
				
			
		}
		int lpos=-1;
		int rpos=-1;
		
		for(int i=0;i<l.size();i++)
		{
			//w.println(l.get(i)+" "+r.get(i));
			if(r.get(i)-l.get(i)+1>max)
			{
				max=r.get(i)-l.get(i)+1;
				lpos=l.get(i);
				rpos=r.get(i);
			}
		}
		
		w.println(lpos+" "+rpos);
		w.close();
	}
	
	static class InputReader {
		
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
		
		public InputReader(InputStream stream) {
			this.stream = stream;
		}
		
		public int read() {
			
			if (numChars==-1) 
				throw new InputMismatchException();
			
			if (curChar >= numChars) {
				
				curChar = 0;
				
				try {
					numChars = stream.read(buf);
				}
				catch (IOException e) {
					throw new InputMismatchException();
				}
				
				if(numChars <= 0)				
					return -1;
			}
			
			return buf[curChar++];
		}
		 
		public String nextLine() {
			
			BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
			String str = "";
	        
			try {
	            str = br.readLine();
	        }
	        catch (IOException e) {
	            e.printStackTrace();
	        }
			
	        return str;
		}
		
		public int nextInt() {
		
			int c = read();
			
			while(isSpaceChar(c)) 
				c = read();
			
			int sgn = 1;
			
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			
			int res = 0;
			
			do {
				if(c<'0'||c>'9') 
					throw new InputMismatchException();
				
				res *= 10;
				res += c - '0';
				c = read();
			}
			while (!isSpaceChar(c)); 
			
			return res * sgn;
		}
		
		public long nextLong() {
			
			int c = read();
			
			while (isSpaceChar(c))
				c = read();
			
			int sgn = 1;
			
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			
			long res = 0;
			
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				
				res *= 10;
				res += c - '0';
				c = read();
			}
			
			while (!isSpaceChar(c));
				return res * sgn;
		}
		
		public double nextDouble() {
			
			int c = read();
			
			while (isSpaceChar(c))
				c = read();
			
			int sgn = 1;
			
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			
			double res = 0;
			
			while (!isSpaceChar(c) && c != '.') {
				
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, nextInt());
				
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				
				res *= 10;
				res += c - '0';
				c = read();
			}
			
			if (c == '.') {
				
				c = read();
				double m = 1;
				while (!isSpaceChar(c)) 
				{
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, nextInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			
			return res * sgn;
		}
		
		public String readString() {
			
			int c = read();
			
			while (isSpaceChar(c))
				c = read();
			
			StringBuilder res = new StringBuilder();
			
			do {
				res.appendCodePoint(c);
				c = read();
			} 
			while (!isSpaceChar(c));
			
			return res.toString();
		}
	 
		public boolean isSpaceChar(int c) {
			
			if (filter != null)
				return filter.isSpaceChar(c);
			
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	 
		public String next() {
			return readString();
		}
		
		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	
	}

	public static void main(String args[]) throws Exception {
		new Thread(null, new cf2(),"cf2",1<<26).start();
	}
}