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:
//package codeforce;

import java.util.LinkedHashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;

/* @author Kbk*/
public class PearlsInARow {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        LinkedHashMap<Integer,Integer> has=new LinkedHashMap();
        HashSet h=new HashSet();
        int temp=1,Count=0;
        for(int i=1;i<=N;i++){
            h.add(sc.nextInt());
            Count++;
            if(h.size()!=Count){
                has.put(temp,i);
                temp=i+1;
                h.clear();
                Count=h.size();
            }
                
        }
        int i=0;
        if(has.size()==0)
            System.out.println(-1);
        else{
            System.out.println(has.size());
            for(Map.Entry etr:has.entrySet()){
                i++;
                if(i==has.size()){
                    int chng=N;
                    has.put((int)etr.getKey(),chng);
                }
                System.out.println(etr.getKey()+" "+etr.getValue());
            }
        }
    }
}