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.DataInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashMap;

/**
 * Created by ProDota2 on 07.01.2016.
 * name of project pcms2contest
 **/
public class Main implements Runnable{
    public void run(){
        Reader in = new Reader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n , k;
        n = in.nextInt();
        k = in.nextInt();

        int a[] = new int[n];

        for(int i = 0;i < n;i++){
            a[i] = in.nextInt();
        }
        int l = 0;
        int r = 0;
        HashMap < Integer , Integer > cnt = new HashMap<Integer, Integer>();
        int ans = 0;
        int start = 0;
        for(int i = 0;i < n;i++){
            if(cnt.size() == k){
                if(ans < r - l + 1){
                    ans = r - l + 1;
                    start = l;
                }
            }
            if(cnt.containsKey(a[i]))
                cnt.put(a[i] , cnt.get(a[i]) + 1);
            else
                cnt.put(a[i] , 1);
            r = i;
            while(cnt.size() > k){
                if(cnt.get(a[l]) == 1)
                    cnt.remove(a[l]);
                else
                    cnt.put(a[l] , cnt.get(a[l]) - 1);
                l++;
            }
        }
        if(cnt.size() == k){
            if(ans < r - l + 1){
                ans = r - l + 1;
                start = l;
            }
        }
        if(ans == 0)
            out.print(1 + " " + n);
        else
            out.print((start + 1) + " " + (start + ans));
        out.close();
    }
    public static void main(String argc[])throws IOException {
        new Thread(new Main()).run();
    }
    class Reader{
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte [] buffer;
        private int bufferPointer, bytesRead;

        public Reader(InputStream in) {
            din = new DataInputStream(in);
            buffer = new byte [ BUFFER_SIZE ];
            bufferPointer = bytesRead = 0;
        }
        public String nextString(int maxSize) {
            byte[] ch = new byte[maxSize];
            int point =  0;
            try {
                byte c = read();
                while (c == ' ' || c == '\n' || c=='\r')
                    c = read();
                while (c != ' ' && c != '\n' && c!='\r') {
                    ch[point++] = c;
                    c = read();
                }
            } catch (Exception e) {}
            return new String(ch, 0,point);
        }
        public int nextInt() {
            int ret =  0;
            boolean neg;
            try {
                byte c = read();
                while (c <= ' ')
                    c = read();
                neg = c == '-';
                if (neg)
                    c = read();
                do {
                    ret = ret * 10 + c - '0';
                    c = read();
                } while (c > ' ');

                if (neg) return -ret;
            } catch (Exception e) {}
            return ret;
        }
        public long nextLong() {
            long ret =  0;
            boolean neg;
            try {
                byte c = read();
                while (c <= ' ')
                    c = read();
                neg = c == '-';
                if (neg)
                    c = read();
                do {
                    ret = ret * 10 + c - '0';
                    c = read();
                } while (c > ' ');

                if (neg) return -ret;
            } catch (Exception e) {}
            return ret;
        }
        private void fillBuffer() {
            try {
                bytesRead = din.read(buffer, bufferPointer =  0, BUFFER_SIZE);
            } catch (Exception e) {}
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }
    }
}