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.Arrays;
import java.util.StringTokenizer;


public class Main {
    static int max = (int) (1e6 + 1);

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt();
        int k = sc.nextInt();
        FenwickTree ft = new FenwickTree(n);
        int[] a = sc.nextIntArray(n);
        int[] lastSeen = new int[max];
        int[] next = new int[n + 1];
        Arrays.fill(next, -1);
        Arrays.fill(lastSeen, -1);
        for (int i = 1; i <= n; i++) {
            int cur = a[i - 1];
            if (lastSeen[cur] == -1) ft.updatePoint(i, 1);
            else
                next[lastSeen[cur]] = i;
            lastSeen[cur] = i;
        }
        int L = 0, R = -1;
        for (int candL = 1; candL <= n; candL++) {
            int candR = ft.query(k);
            if (candR - candL > R - L) {
                L = candL;
                R = candR;
            }
            ft.updatePoint(candL, -1);
            ft.updatePoint(next[candL], 1);
        }
        out.println(L + " " + R);
        out.close();
        out.flush();

    }

    static class FenwickTree {
        int n, ft[];

        public FenwickTree(int n) {
            this.n = n;
            ft = new int[n + 1];
        }

        void updatePoint(int idx, int val) {
            if (idx == -1) return;
            while (idx <= n) {
                ft[idx] += val;
                idx += idx & -idx;
            }
        }

        int query(int val) {
            int idx = 0;
            int range = n;
            while ((range & range - 1) != 0) range ^= range & -range;
            while (range > 0) {
                int cand = idx + range;
                if (cand <= n && val >= ft[cand]) {
                    val -= ft[cand];
                    idx = cand;
                }
                range >>= 1;
            }
            return idx;
        }
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }


        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public char nextChar() throws IOException {
            return next().charAt(0);
        }

        public Long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }


        public int[] nextIntArray(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) throws IOException {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }


        public Integer[] nextIntegerArray(int n) throws IOException {
            Integer[] a = new Integer[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public double[] nextDoubleArray(int n) throws IOException {
            double[] ans = new double[n];
            for (int i = 0; i < n; i++)
                ans[i] = nextDouble();
            return ans;
        }

        public short nextShort() throws IOException {
            return Short.parseShort(next());
        }

    }

}