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.math.BigInteger;
import java.util.*;
     
     
    public class ContestMode1 {
     
    	static double eps=(double)1e-6;
    	static long mod=(int)1e9+7;
    	public static void main(String args[]) throws FileNotFoundException, UnsupportedEncodingException{
    		InputReader in = new InputReader(System.in);
    		OutputStream outputStream = System.out;
    		PrintWriter out = new PrintWriter(outputStream);
    		//----------My Code Starts Here----------
    		int n=in.nextInt();
    		int a[]=new int[n];
    		for(int i=0;i<n;i++){
    			a[i]=in.nextInt();
    		}
    		HashMap<Integer,Integer> h=new HashMap<Integer,Integer>();
    		ArrayList<Integer> ans=new ArrayList<Integer>();
    		int tmp=0;
    		for(int i=0;i<n;i++){
    			tmp++;
    			if(h.containsKey(a[i])){
    				int extra=0,start=h.get(a[i]);
    				if(i+1-start+1<tmp)
    					extra+=tmp-(i+1-start+1);
    				ans.add(start-extra);
    				ans.add(i+1);
    				h.clear();
    				tmp=0;
    			}
    			else{
    				h.put(a[i], i+1);
    			}
    		}
    		if(tmp>0){
    			if(ans.size()>0){
    				ans.remove(ans.size()-1);
    				ans.add(n);
    			}
    		}
    		if(ans.size()==0){
    			System.out.println("-1");
    			return;
    		}
    		else{
    			out.println(ans.size()/2);
    			for(int i=0;i<ans.size();i+=2){
    				out.println(ans.get(i)+" "+ans.get(i+1));
    			}
    		}
    		out.close();
    		//---------------The End------------------
    	}
    	
    	static long modulo(long a,long b,long c) {
    	    long x=1;
    	    	    long y=a;
    	    	    while(b > 0){
    	    	        if(b%2 == 1){
    	    	            x=(x*y)%c;
    	    	        }
    	    	        y = (y*y)%c; // squaring the base
    	    	        b /= 2;
    	    	    }
    	    	    return  x%c;
    	    	}
    	static long gcd(long x, long y)
        {
            long r=0, a, b;
            a = (x > y) ? x : y; // a is greater number
            b = (x < y) ? x : y; // b is smaller number
            r = b;
            while(a % b != 0)
            {
                r = a % b;
                a = b;
                b = r;
            }
            return r;
        }
    	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());
    	    }
    	  }
    }