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: Akshay Miterani
     * DA-IICT
     */
    import java.io.*;
    import java.util.*;
    
     
    public class MainB {
     
    	static double eps=(double)1e-6;
    	static long mod=(int)1e9+7;
    	static HashMap<Long,Integer> h=new HashMap<Long,Integer>();
    	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();
    		int k=in.nextInt();
    		int a[]=new int[n];
    		for(int i=0;i<n;i++)
    			a[i]=in.nextInt();
    		int ptr=0;
    		int max=0,maxi=0,maxj=0;
    		HashMap<Integer,Integer> h=new HashMap<Integer,Integer>();
    		for(int i=0;i<n;i++){
    			if(h.containsKey(a[i])){
    				h.put(a[i], h.get(a[i])+1);
    				if(h.size()<=k){
    					if(i-ptr+1>max){
    						max=i-ptr+1;
    						maxi=ptr+1;
    						maxj=i+1;
    					}
    				}
    			}
    			else{
    				h.put(a[i],1);
    				while(h.size()>k && ptr<n){
    					if(!h.containsKey(a[ptr])){
    						ptr++;
    						continue;
    					}
    					if(h.get(a[ptr])==1){
    						h.remove(a[ptr]);
    					}
    					else{
    						h.put(a[ptr], h.get(a[ptr])-1);
    					}
    					ptr++;
    				}
    				if(h.size()<=k){
    					if(i-ptr+1>max){
    						max=i-ptr+1;
    						maxi=ptr+1;
    						maxj=i+1;
    					}
    				}
    			}
    		}
    		out.println(maxi+" "+maxj);
    		out.close();
    		//---------------The End------------------
    	}
    	
    	static class Pair implements Comparable<Pair>{
    		long x;
    		long y;
    		int i;
    		Pair(long xx,long yy){
    			x=xx;
    			y=yy;
    		}
    		@Override
    		public int compareTo(Pair o) {
    			if(this.y==o.y)
					return Long.compare((this.x),(o.x));
				else
					return Long.compare((this.y),(o.y));
    		}
    	}
    	
    	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());
    	    }
    	  }
    }