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.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void solve() {
        int n = IO.readInt();
        int k = IO.readInt();
        int[] a = IO.readIntArray(n);
        int l = 0;
        int r = 0;
        int d = 0;
        int ml = 0;
        int mr = 0;
        int[] lastPositions = new int[1000001];
        for (r = 0; r < n; ++r) {
            int last = lastPositions[a[r]] - 1;
            lastPositions[a[r]] = r + 1;

            if (last < l) {
                d++;
                if (d == k + 1) {
                    while (l != lastPositions[a[l]] - 1) {
                        l++;
                    }
                    l++;
                    d--;
                }
            }

            if (r - l > mr - ml) {
                mr = r;
                ml = l;
            }
        }

        ml++;
        mr++;
        IO.println(ml + " " + mr);
    }

    // Input/Output ================================
    public static class IO {

        private static Scanner scanner;
        private static PrintWriter writer;

        public static void setUp(InputStream in, OutputStream out) {
            scanner = new Scanner(new java.io.BufferedInputStream(in));
            writer = new PrintWriter(out);
        }

        public static boolean isEmpty() {
            return !scanner.hasNext();
        }

        public static boolean hasNextLine() {
            return scanner.hasNextLine();
        }

        public static String readLine() {
            String line;
            try {
                line = scanner.nextLine();
            }
            catch (Exception e) {
                line = null;
            }
            return line;
        }

        public static String readString() {
            return scanner.next();
        }

        public static int readInt() {
            return scanner.nextInt();
        }

        public static int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int index = 0; index < n; ++index) {
                a[index] = readInt();
            }
            return a;
        }

        public static Pair<Integer, Integer>[] readIntArrayWithIndexes(int n) {
            Pair<Integer, Integer>[] a = new Pair[n];
            for (int index = 0; index < n; ++index) {
                a[index] = new Pair<>(index, readInt());
            }
            return a;
        }

        public static double readDouble() {
            return scanner.nextDouble();
        }

        public static float readFloat() {
            return scanner.nextFloat();
        }

        public static long readLong() {
            return scanner.nextLong();
        }

        public static char readChar() {
            return scanner.findInLine("[^\\s]").charAt(0);
        }

        public static void print(Object o) {
            writer.print(o);
            writer.flush();
        }

        public static void println(Object o) {
            writer.println(o);
            writer.flush();
        }
    }

    // Algorithms ================================

    private static class Algo {

        private static int binSearch(int[] array, int n, int lo, int hi) {
            if (lo > hi) {
                return lo;
            }

            int mid = lo + (hi - lo) / 2;
            int cmp = (int) java.lang.Math.signum(n - array[mid]);
            if (cmp < 0) {
                return binSearch(array, n, lo, mid - 1);
            }
            else if (cmp == 0) {
                return mid;
            }
            else {
                return binSearch(array, n, mid + 1, hi);
            }
        }

        private static void permutations(int n) {
            int[] p = new int[n];
            for (int index = 0; index < n; ++index) {
                p[index] = index + 1;
            }

            while (true) {
                IO.println(Arrays.toString(p));

                int k = n - 1;
                while (k > 0) {
                    if (p[k] < p[k - 1]) {
                        k--;
                    }
                    else {
                        break;
                    }
                }
                if (k == 0) {
                    break;
                }
                int j = n - 1;
                while (p[j] < p[k - 1]) {
                    j--;
                }

                int t = p[j];
                p[j] = p[k - 1];
                p[k - 1] = t;

                int i = 0;
                while (k + i < n - 1 - i) {
                    t = p[k + i];
                    p[k + i] = p[n - i - 1];
                    p[n - i - 1] = t;
                    i++;
                }
            }
        }

        private static boolean isPrime(int number) {
            if (number <= 1) {
                return false;
            }
            if (number <= 3) {
                return true;
            }
            if (number % 2 == 0 || number % 3 == 0) {
                return false;
            }
            int i = 5;
            while (i * i <= number) {
                if (number % i == 0 || number % (i + 2) == 0) {
                    return false;
                }
                i += 6;
            }
            return true;
        }

        private static boolean isPrimeOrOne(int number) {
            return number == 1 || isPrime(number);
        }

        private static boolean isPalindrome(int number) {
            int n = number;
            int reverse = 0;
            while (n > 0) {
                reverse *= 10;
                reverse += (n % 10);
                n /= 10;
            }
            return reverse == number;
        }

        public static int gcd(int a, int b) {
            while (b != 0) {
                int tmp = a % b;
                a = b;
                b = tmp;
            }
            return a;
        }
    }

    private static class Math2 {

        static long c(int n, int k) {
            if (n == 0 && k == 0) {
                return 1;
            }
            int d = 1000;
            int l = 1000000007;
            long[][] c = new long[d + 1][d + 1];
            for (int i = 1; i <= d; ++i) {
                for (int j = 0; j <= i; ++j) {
                    if (i == j || j == 0) {
                        c[i][j] = 1;
                    }
                    else {
                        c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % l;
                    }
                }
            }
            return c[n][k];
        }
    }

    static class Pair<K, V> {
        K key;
        V value;

        Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        IO.setUp(System.in, System.out);
        /*
        try {
            IO.setUp(new FileInputStream("encode.in"), new FileOutputStream("encode.out"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            return;
        }
        */
        solve();
    }
}