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.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Double.parseDouble;
import static java.lang.String.*;
   

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
                                            //(new FileReader("input.in"));
        StringBuilder out = new StringBuilder();
        StringTokenizer tk;
        Reader.init(System.in);
        //PrintWriter pw = new PrintWriter("output.out", "UTF-8");
       
        tk = new StringTokenizer(in.readLine());
        int n = parseInt(tk.nextToken());
        int k = parseInt(tk.nextToken());
        
        int [] A = new int[n];
        int [] vis = new int[1000001];
        int i;
        tk = new StringTokenizer(in.readLine());
        for(i=0; i<n; i++)
            A[i] = parseInt(tk.nextToken());
        
        int l = 0,r = 0,a = 0,b = 0,mx = -1,cnt=0;
        int x;
        
        while(r<n && l<=r) {
            if(cnt > k) {
                vis[A[l]]--;
                if(vis[A[l]]==0) cnt--;
                l++;
            } else {
                if(vis[A[r]]==0) cnt++;
                vis[A[r]]++;
                r++;
                if(cnt<=k && r-l > mx) {
                    a = l;
                    b = r;
                    mx = r-l;
                }
            }
        }
        
        a++;
        
        System.out.println(a+" "+b);
    }
    
}

class Tools {
    
    public static boolean next_permutation(int [] p,int len) {
        int a =len-2;
        while(a>=0 && p[a]>=p[a+1])
            a--;
        
        if(a==-1)
            return false;
        
        int b = len-1;
        while(p[b]<=p[a])
            b--;
        
        p[a] += p[b];
        p[b] = p[a] - p[b];
        p[a] -= p[b];
        
        for(int i=a+1, j=len-1; i<j; i++,j--) {
            p[i] += p[j];
            p[j] = p[i]-p[j];
            p[i] -= p[j];
        }
        
        return true;
    }
    
}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) throws UnsupportedEncodingException {
        reader = new BufferedReader(
                     new InputStreamReader(input, "UTF-8") );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }
    
    static String nextLine() throws IOException {
        return reader.readLine();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
    
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
}