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.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import static java.lang.Math.*;
import java.util.StringTokenizer;




public class Shahriar {

    /**
     * @param args the command line arguments
     */
    public static int []arr;
    public int lower_bound(int []a,int n,int v) {
        int ans = -1;
        
        return ans;
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO code application logic 
        Scanner in = new Scanner(System.in);
        HashSet<Integer> set = new HashSet<>();
        int n = in.nextInt();
        int [] a = new int[n+10];
        for(int i=1;i<=n;i++) a[i] = in.nextInt();
        int ans = 0;
        int [] lt = new int[n+10];
        int [] rt = new int[n+10];
        lt[0] = rt[0] = -1;
        for(int i=1;i<=n;i++) {
            int k = a[i];
            //System.out.println(k);
            if(set.contains(k)) {
                rt[ans] = i;
                set.clear();
                ans++;
                lt[ans] = rt[ans] = -1;
            }
            else {
                if(lt[ans]==-1) lt[ans] = i;
                set.add(k);
            }
        }
        if(lt[ans]!=-1&&rt[ans]==-1&&ans>0) {
            rt[ans-1] = n;
        }
        //System.out.println("here");
        if(ans==0) System.out.println(-1);
        else {
            System.out.println(ans);
            for(int i=0;i<ans;i++) {
                System.out.println(lt[i] + " " + rt[i]);
            }
        }
    }
}