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:
//      これを翻訳している間、あなたはあなたの人生のいくつかの貴重な瞬間を無駄にしました
//  DO something instead of nothing

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Solution {
    static PrintWriter fop = new PrintWriter(System.out);




    public static void main(String[] args) {
        FastScanner fsca = new FastScanner();


        int n = fsca.nextInt() ;
        int a[] = fsca.readArray(n);
       // int dp[] = new int[300009] ;
        LinkedHashSet<Integer> set = new LinkedHashSet<>() ;



        ArrayList<Integer> list = new ArrayList<>() ;
        int prev = 0 ;
        list.add(0);
        int cnt = 0 ;

        for (int i = 0; i <n ; i++) {
   //         dp[a[i]]++ ;
            boolean flag = false ;
            if (set.contains(a[i])){
                flag = true ;
            }
            else set.add(a[i]) ;

            if (i == n-1){

                if (flag){
                    list.add(i);
                    cnt++;
                }
                else{
                    if (cnt == 0)
                        continue;
                    list.remove(list.size()-1) ;
                    list.remove(list.size()-1) ;
                    list.add(i);
                }
                continue;
            }


            if (flag){
                cnt++ ;
                list.add(i);
                list.add(i+1) ;
                prev = i+1 ;
                set.clear();
            }
        }
        if (cnt == 0){
            System.out.println(-1);
            return;
        }

        System.out.println(cnt);
        for (int i = 0; i <list.size()-1 ; i+= 2) {
            fop.append( (list.get(i)+1) + " " + (list.get(i+1)+1) + "\n") ;
        }














        fop.flush();
        fop.close();


    }
    /*-----------------------------------------------------------------------------------------------------------------------------------------------*/


    static long gcd(long a, long b) {
        return (b == 0) ? a : gcd(b, a % b);
    }

    ;

    static int gcd(int a, int b) {
        return (b == 0) ? a : gcd(b, a % b);
    }


    static final Random random = new Random();

    static void ruffleSort(int[] a) {
        int n = a.length;//shuffle, then sort
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n), temp = a[oi];
            a[oi] = a[i];
            a[i] = temp;
        }
        Arrays.sort(a);
    }

    static void ruffleSort(long[] a) {
        int n = a.length;//shuffle, then sort
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n);
            long temp = a[oi];
            a[oi] = a[i];
            a[i] = temp;
        }
        Arrays.sort(a);
    }


    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[][] readMat(int n, int m) {
            int a[][] = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    a[i][j] = nextInt();
            return a;
        }

        char[][] readCharMat(int n, int m) {
            char a[][] = new char[n][m];
            for (int i = 0; i < n; i++) {
                String s = next();
                for (int j = 0; j < m; j++)
                    a[i][j] = s.charAt(j);
            }
            return a;
        }


        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long[] readLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    static void print(int a[], int n) {
        for (int i = 0; i < n; i++)
            fop.append((a[i]) + " ");
        // fop.append("\n") ;
    }

    static void print(long a[], int n) {
        for (int i = 0; i < n; i++)
            fop.append((a[i]) + " ");
        // fop.append("\n") ;
    }
}