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.StringTokenizer;

public class kgood {
    public static int MAX = (int) 1e6;
    public static void main(String[] args) throws IOException {
        Kattio io = new Kattio();
        int N = io.nextInt();
        int K = io.nextInt();

        int[] A = new int[MAX];
        int[] freq = new int[MAX]; // Frequency of each number in the window.
        int difVal = 0; // Number of different values in the window.
        int left = 0;

        int maxLen = 0;
        int maxL = 0;
        int maxR = 0;


        for (int i = 0; i < N; i++) {
            int x = A[i] = io.nextInt();
            // Increment the frequency of the number.
            if (freq[x] == 0) {
                freq[x] = 1;
                difVal++;
            } else {
                freq[x]++;
            }

            // If the window isn't valid, shift the left bound rightwards.
            while (difVal > K) {
                freq[A[left]]--;
                if (freq[A[left]] == 0) {
                    difVal--;
                }
                left++;
            }

            // Update the window length.
            int curLen = i - left + 1;
            if (curLen > maxLen) {
                maxLen = curLen;
                maxL = left;
                maxR = i;
            }
        }

        System.out.println((maxL + 1) + " " + (maxR + 1));

    }

    static class Kattio extends PrintWriter {
        private BufferedReader r;
        private StringTokenizer st;

        // standard input
        public Kattio() { this(System.in, System.out); }
        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }
        // USACO-style file input
        public Kattio(String problemName) throws IOException {
            super(new FileWriter(problemName + ".out"));
            r = new BufferedReader(new FileReader(problemName + ".in"));
        }

        // returns null if no more input
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }

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