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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class cfvc13
{
	static BufferedReader reader;
    static StringTokenizer tokenizer;
    static void init(InputStream input) 
    {
        reader = new BufferedReader( new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
    static String next() throws IOException
    {
        while ( ! tokenizer.hasMoreTokens() )
        {
            tokenizer = new StringTokenizer(reader.readLine() );
        }
        return tokenizer.nextToken();
    }
 
    static long nextInt() throws IOException 
    {
        return Long.parseLong( next() );
    }
	static PrintWriter writer;
	static void outit(OutputStream outputStream)
	{
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}
	static void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}
 
	static void println(Object...objects) {
		print(objects);
		writer.println();
	}
 
	static void close() {
		writer.close();
	}
 
	static void flush() {
		writer.flush();
	}
    public static void main(String [] args) throws IOException
    {
    	init(System.in) ;
    	outit(System.out) ;
//    	int t = (int) nextInt() ;
//    	for(int i = 0 ; i<t ; i++)
    	output() ;
        flush();
        close();
    }
    public static void output() throws IOException
    {
    	int n = (int) nextInt() ;
    	int [] a = new int [n] ;
    	for(int i = 0 ; i<n ; i++)
    	{
    		a[i] = (int) nextInt() ;
    	}
    	ArrayList<Integer> br = new ArrayList<Integer>() ;
    	HashMap<Integer,Integer> ctr = new HashMap<Integer,Integer>() ;
    	for(int i = 0 ;i<n ; i++)
    	{
    		if(ctr.containsKey(a[i]))
    		{
    			ctr.put(a[i],ctr.get(a[i])+1) ;
    		}
    		else
    		{
    			ctr.put(a[i],1);
    		}
    		if(ctr.get(a[i])==2)
    		{
    			br.add(i) ;
    			ctr = new HashMap<Integer,Integer>() ;
    		}
    	}
//    	for(int i = 0 ;i<br.size();i++)
//    	{
//    		println((br.get(i)+1)) ;
//    	}
    	int s = br.size();
    	if(s==0)
    	{
    		println(-1) ;
    	}
    	else
    	{
    	println(s) ;
    	if(s==1)
    	{
    		println(1+" "+n) ;
    	}
    	else
    	{
    	println(1+" "+(br.get(0)+1)) ;
    	for(int i = 0; i<(s-2); i++)
    	{
    		println((br.get(i)+2)+" "+(br.get(i+1)+1)) ;
    	}
    	println((br.get(s-2)+2)+" "+n) ;
    	}
    	}
    }
}