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 static java.lang.Integer.max;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Short.parseShort;
import static java.lang.Byte.parseByte;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Contest {

    static int nextInt() throws IOException {
        return parseInt(next());
    }

    static long nextLong() throws IOException {
        return parseLong(next());
    }

    static short nextShort() throws IOException {
        return parseShort(next());
    }

    static byte nextByte() throws IOException {
        return parseByte(next());
    }

    static String next() throws IOException {
        while (tok == null || !tok.hasMoreTokens())
            tok = new StringTokenizer(in.readLine());
        return tok.nextToken();
    }

    static String nextLine() throws IOException {
        return in.readLine();
    }

    private static BufferedReader in;
    private static StringTokenizer tok;
    private static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) throws Exception {
        in = new BufferedReader(new InputStreamReader(System.in));

        /*--------------------SolutionStarted-------------------*/
        solve();
        /*--------------------SolutionEnded--------------------*/

        in.close();
        out.close();
    }
    static void solve() throws IOException {
        int []a =new int[nextInt()];
        int k = nextInt(), l=0, r=0, max = Integer.MIN_VALUE, left = 0, right = 0, freq;
        Set<Integer> segment = new HashSet<>(1000009);
        Map<Integer, Integer> freqMap = new HashMap<>();
        boolean flag;
        for (int i = 0; i <a.length ; i++)
            a[i]=nextInt();
        while(l<a.length&&r<a.length) {
            flag = false;
            segment.add(a[r]);
            if (segment.size() > k) {
                while (!flag) {
                    freq = freqMap.get(a[l]);
                    if (freq == 1) {
                        freqMap.remove(a[l]);
                        segment.remove(a[l]);
                        flag = true;
                    } else {
                        freqMap.put(a[l], freq-1);
                    }
                    l++;
                }
            }
            if (freqMap.containsKey(a[r])){
                freqMap.put(a[r], freqMap.get(a[r])+1);
            }else{
                freqMap.put(a[r], 1);
            }
            if (segment.size() <= k) {
                if (r - l > max) {
                    max = r - l;
                    left = l;
                    right = r;
                }
            }
            r++;
        }
        out.println((left+1)+" "+(right+1));
    }
}
class IntPair implements Comparable<IntPair> {
    int key, value;

    IntPair() {
    }

    IntPair(int key, int value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public int compareTo(IntPair o) {
        return key - o.key;
    }

    public String toString() {
        return key + " " + value;
    }
}
class BooleanPair {
    boolean key, value;

    BooleanPair() {
    }

    BooleanPair(boolean key, boolean value) {
        this.key = key;
        this.value = value;
    }
}