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

public class Main{
    public static void main(String[] args)throws Throwable{
        Escanner sc = new Escanner();
        out = new PrintWriter(System.out);
        //////////  
        int n = sc.nextInt(); 
        int arr[] = new int[n];

        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();

        int cnt = 0;
        int[][] ans = new int[n][2];

        HashSet<Integer> set = new HashSet<Integer>();
        int strt = 1;
        for(int i=0; i<n; i++)
            if(!set.add(arr[i])){
                ans[cnt][0] = strt;
                ans[cnt][1] = i+1;
                cnt++;
                strt = i+2;
                set.clear();
            }
        if(cnt==0)
            out.println(-1);
        else{
            out.println(cnt);
            for(int i=0; i<cnt; i++)
                out.println(ans[i][0]+" "+(i+1==cnt?n:ans[i][1]));
        }


        //////////
        out.close();
    }
    static class Escanner {
        BufferedReader in;
        StringTokenizer st;

        Escanner() throws Throwable {
            in = new BufferedReader(new InputStreamReader(System.in),32768);
            st = new StringTokenizer("");
        }
        Escanner(String fileName) throws Throwable {
            in = new BufferedReader(new FileReader(fileName),32768);
            st = new StringTokenizer("");
        }

        boolean isBlank() throws Throwable{
            String l = in.readLine();
            st = new StringTokenizer(l==null?"":l);
            return !st.hasMoreTokens();
        }

        boolean EOL(){
            return !st.hasMoreTokens();
        }

        String nextStr() throws Throwable {
            while(!st.hasMoreTokens())
                st = new StringTokenizer(in.readLine());
            return st.nextToken();
        }

        int nextInt() throws Throwable {
            return Integer.parseInt(nextStr());
        }

        long nextLong() throws Throwable {
            return Long.parseLong(nextStr());
        }

        BigInteger nextBigInt() throws Throwable {
            return new BigInteger(nextStr());
        }

        double nextDouble() throws Throwable {
            return Double.parseDouble(nextStr());
        }
    }
    static PrintWriter out;
}