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.awt.*;
import java.awt.geom.*;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.List;

/**
 * Created by ribra on 11/15/2015.
 */
public class Main {

    private static InputReader sc = new InputReader(System.in);
    private static PrintWriter pw = new PrintWriter(System.out);
    private static long timeBegin, timeEnd;
    private static long memoryTotal, memoryFree;



    public static void main(String [] args) {
        timeBegin = System.currentTimeMillis();
        memoryTotal = Runtime.getRuntime().freeMemory();

        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        List<Pair> list = new ArrayList<>();

        Map<Integer, Integer> map = new HashMap<>(); // number / position
        map.put(arr[0], 1);
        for (int i = 1; i < n; i++) {
            int number = arr[i];
            boolean exist = map.containsKey(number);
            if (!exist) map.put(number, i + 1);
            else {
                int prPos = map.get(number);
                list.add(new Pair(prPos, i + 1));
                map.clear();
            }
        }

        if (list.isEmpty()) pw.print(-1);
        else if (list.size() == 1) {
            pw.println(1);
            pw.print(1 + " " + n);
        }
        else {
            pw.println(list.size());
            int last = 0;
            int m = list.size();
            for (int i = 0; i < m; i++) {
                Pair cur = list.get(i);
                if (i == 0) cur.a = 1;
                else if (i == m - 1) cur.b = n;
                if (i + 1 < m) {
                    Pair next = list.get(i + 1);
                    next.a = cur.b + 1;
                }
                pw.println(cur.a + " " + cur.b);
                last = cur.b;
            }

        }


        checker();
        terminate();
    }


    static class Pair {
        int a;
        int b;

        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }


    }

    public static void checker() {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            System.out.println();
            time();
            memory();
        }
    }
    public static void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }
    public static void memory() {
        memoryFree = Runtime.getRuntime().freeMemory();
        System.err.println("Memory = " + ((memoryTotal - memoryFree) >> 10)
                + " KB");
    }
    public static void terminate() {
        pw.close();
    }


    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }
}