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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.StringTokenizer;


public class _ECR_3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyfScanner in=new MyfScanner();
		PrintWriter pw=new PrintWriter(System.out);
		int n=in.nextInt();
		long a[]=new long[n];
		for(int i=0;i<n;i++)
		{
			a[i]=in.nextLong();
		}
		Hashtable<Long,Integer> hs=new Hashtable<Long,Integer>();
		ArrayList<Integer> list=new ArrayList<Integer>();
		int ans=0;
		list.add(0);
		for(int i=0;i<n;i++)
		{
			//System.out.println(hs.values());
			if(hs.containsKey(a[i]))
			{
				//System.out.println("here");
				ans++;
				int temp=hs.get(a[i]);
				list.add(i);
				list.add(i+1);
				hs.clear();
			}
			else
				hs.put(a[i],i);
		}
		if(ans==0)
			pw.println(-1);
		else
		{
			System.out.println(ans);
			for(int i=0;i<list.size()-1;i+=2)
			{
				if(i==list.size()-3)
				pw.print((list.get(i)+1)+" "+n);
				else
					pw.print((list.get(i)+1)+" "+(list.get(i+1)+1));
				pw.println();
			}
		}
		pw.close();
		
		
		
		
		
	}

}
class node implements Comparable<node>
{
	int ind;
	long value;
	public node(int i,long v)
	{
		ind=i;
		value=v;
	}
	public int compareTo(node n)
	{
		return Long.compare(this.value,n.value);
	}
}
class MyfScanner {
	   BufferedReader br;
	   StringTokenizer st;
	  
	   public MyfScanner() {
	      br = new BufferedReader(new InputStreamReader(System.in));
	   }
	  
	   String next() {
	      while (st == null || !st.hasMoreElements()) {
	         try {
	            st = new StringTokenizer(br.readLine());
	         } catch (IOException e) {
	            e.printStackTrace();
	         }
	      }
	      return st.nextToken();
	   }
	  
	   int nextInt() {
	      return Integer.parseInt(next());
	   }
	  
	   long nextLong() {
	      return Long.parseLong(next());
	   }
	  
	   double nextDouble() {
	      return Double.parseDouble(next());
	   }
	  
	   String nextLine(){
	      String str = "";
	      try {
	         str = br.readLine();
	      } catch (IOException e) {
	         e.printStackTrace();
	      }
	      return str;
	   }
	 
	}