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.util.*;
   import java.io.*;

public class Solution {
  // static int dp[][]=new int[10001][10001];
  static int pos=0;
     static ArrayList<Integer> graph[];
     static int diff[];
     static int dp[];
     static ArrayList<Integer> newgraph[];
     static int parent[];
     static boolean vis[];
     static int k;
     static int seive[]=new int[1000001];
     static int dis[]=new int[1000001];
     static int subtree[]=new int[1000001];
     static int N =1000001;
     static HashSet<String> hm=new HashSet<>();
     static HashSet<String> hm1=new HashSet<>();
     static HashMap<Integer, Character> hash=new HashMap<>();
     static Stack<Integer> st=new Stack<>();
     static int time=0;
     static int components=0;
     public static void main(String[] args) {
       Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
       StringBuilder sb=new StringBuilder();
       int n=sc.nextInt();
       int k=sc.nextInt();
       int a[]=new int[n];
       for( int i=0;i<n;i++)
       {
         a[i]=sc.nextInt();
       }
       int count_distinct=0;
       int p=0;
       int q=-1;
       int max=0;
int start=-1;
int end=-1;
       HashMap<Integer, Integer> hm=new HashMap<>();
       for( int i=0;i<n;i++)
       {
         if(!hm.containsKey(a[i]))
         {
           count_distinct++;
           hm.put(a[i],1);
         }
         else
         {
           hm.put(a[i],hm.get(a[i])+1);
         }
         q++;
         if(count_distinct<=k)
         {
           if(max<q-p+1)
           {
             start=p+1;
             end=q+1;
             max=q-p+1;
           }
         }
         else if(count_distinct>k)
         {
           while(count_distinct>k)
           {
             int val=hm.get(a[p]);
             val--;
             if(val==0)
             {
               hm.remove(a[p]);
               count_distinct--;
             }
             else
             hm.put(a[p],val);
             p++;
           }
         }
       }
       System.out.println(start+" "+end);

     }




}

class Pair
{
long x,y;
Pair(long x, long y)
{
this.x=x;
this.y=y;
}
}
class myComparator implements Comparator<Pair>
{
public int compare(Pair a, Pair b)
{
return Long.compare(b.y, a.y);
}
}