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.lang.*;
import java.math.*;
import java.io.*;
import java.text.*;
public class Rough{
   
    static PrintWriter w=new PrintWriter(System.out);
    public static void main(String [] args){
        DecimalFormat dm=new DecimalFormat("0.000000");
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int arr[]=new int[n+1];
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextInt();
        }
        int j=1,left=0,right=0,max=Integer.MIN_VALUE;
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=1;i<=n;i++){
            if(map.containsKey(arr[i])){
                map.replace(arr[i],map.get(arr[i])+1);
            }
            else{
                map.put(arr[i],1);
            }
            while(map.size()>k&&j<n){
                if(map.get(arr[j])==1){
                    map.remove(arr[j]);
                }
                else{
                    map.replace(arr[j],map.get(arr[j])-1);
                    
                }
                j++;
            }
            if((i-j)>max){
                left=j;
                right=i;
                max=i-j;
            }
        }
        w.println(left+" "+right);
        w.close();
    }
}