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.*;
import java.util.*;
import java.text.*;
import java.lang.*;
import java.math.BigInteger;
import java.util.regex.*;

public class Main {
     static ArrayList a[]=new ArrayList[3000001];
     static long mod=1000000007L;
     public static void main(String[]args) throws IOException
    {
       InputReader in=new InputReader(System.in);
       PrintWriter pw=new PrintWriter(System.out);
       int n=in.nextInt();
       int k=in.nextInt();
       long a[]=new long[n];
       for(int i=0;i<n;i++)
    	   a[i]=in.nextLong();
       HashMap<Long,Integer>hm=new HashMap<>();
       int l=0;
       int r=0;
       int ans[]=new int[2];
       int len=0;
       while(r<n) {
    	   
    	   if(hm.size()<=k) {
    		   if(hm.containsKey(a[r])) {
        		   hm.put(a[r], hm.get(a[r])+1);
        	   }
        	   else
        		   hm.put(a[r], 1);
    		   r++;
    	   }
    	   else {
    		   while(hm.size()>k) {
    			   
	    		   int get=hm.get(a[l]);
	    		   if(get==1) {
	    			   hm.remove(a[l]);
	    		   }
	    		   else
	    		   {
	    			   hm.put(a[l], get-1);
	    		   }
	    		   l++;
    		   }
    	   }
    	   if(l==r)
    		   r++;
    	   if(len<r-l && hm.size()<=k) {
    		   len=r-l;
    		   ans[0]=l;
    		   ans[1]=r-1;
    	   }
       }
       pw.println((ans[0]+1)+" "+(ans[1]+1));
       pw.flush();
       pw.close();
    }
    private static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
   static class InputReader 
        {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream) 
        { 
            this.stream = stream;
        }
        public int snext() 
        {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) 
            {
                curChar = 0;
                try 
                {
                    snumChars = stream.read(buf);
                } 
                
                catch (IOException e) 
                {
                    throw new InputMismatchException();
                }
                
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int nextInt() 
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public long nextLong()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public int[] nextIntArray(int n) 
        {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) 
            {
                a[i] = nextInt();
            }
            return a;
        }
        static class tri implements Comparable<tri> {
            int p, c, l;
 
            tri(int p, int c, int l) {
                this.p = p;
                this.c = c;
                this.l = l;
            }
 
            public int compareTo(tri o) {
                return Integer.compare(l, o.l);
            }
        }
 
        public String readString()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        public String nextLine() 
        {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(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;
        }
 
        private boolean isEndOfLine(int c) 
        {
            return c == '\n' || c == '\r' || c == -1;
        }
 
        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }
   public static long modularExponentiation(long x,long n,long M)
   {
       long result=1;
       while(n>0)
       {
           if(n % 2 ==1)
               result=(result%M * x%M)%M;
           x=(x%M * x%M)%M;
           n=n/2;
       }
       return result;
   }
   
   public static long modInverse(int A,int M)
   {
       return modularExponentiation(A,M-2,M);
   }
   
   public static long modInverse(long A,long M)
   {
       return modularExponentiation(A,M-2,M);
   }
   static class pair implements Comparable<pair>
   {
       Long x, y;
       pair(long x,long y)
       {
           this.x=x;
           this.y=y;
       }

       public int compareTo(pair o) {
           int result = x.compareTo(o.x);
           if(result==0)
               result = y.compareTo(o.y);

           return result;
       }

       public String toString()
       {
           return x+" "+y;
       }

       public boolean equals(Object o)
       {
           if (o instanceof pair)
          {
               pair p = (pair)o;
               return (Math.abs(p.x-x)==0 && Math.abs(p.y-y)==0);
           }
           return false;
       }

       public int hashCode()
       {
           return new Long(x).hashCode()*31 + new Long(y).hashCode();
       }
   }
   
    public static long[] shuffle(long[] a, Random gen){ 
        for(int i = 0, n = a.length;i < n;i++){ 
            int ind = gen.nextInt(n-i)+i; 
            long d = a[i]; 
            a[i] = a[ind]; 
            a[ind] = d; 
        } 
        return a; 
    }

    public static int GCD(int a,int b)
	{
		if(b==0)
			return a;
		else
			return GCD(b,a%b);
	}
	
	public static long GCD(long a,long b)
	{
		if(b==0)
			return a;
		else
			return GCD(b,a%b);
	}
}


class dsu{
	int parent[];
	ArrayList a[];
	dsu(int n){
		parent=new int[n+1];
		a=new ArrayList[n+1];
		for(int i=0;i<=n;i++)
		{
			parent[i]=i;
			a[i]=new ArrayList<Integer>();
			a[i].add(i);
		}
	}
	int root(int n) {
		while(parent[n]!=n)
		{
			parent[n]=parent[parent[n]];
			n=parent[n];
		}
		return n;
	}
	void union(int _a,int _b) {
		int p_a=root(_a);
		int p_b=root(_b);
	/*	if(a[p_a].size()>a[p_b].size()) {
			for(int i=0;i<a[p_b].size();i++) {
				a[p_a].add(a[p_b].get(i));
			}
			a[p_b].clear();
		}
		else
		{
			parent[p_a]=p_b;
			for(int i=0;i<a[p_a].size();i++) {
				a[p_b].add(a[p_a].get(i));
			}
			a[p_a].clear();
		}*/
		parent[p_b]=p_a;
	}
	boolean find(int a,int b) {
		if(root(a)==root(b))
			return true;
		else
			return  false;
	}
	long size(int n) {
		return (a[n].size());
	}
	
}