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


public class ProblemA {
    public static void main(String[] args) {
        int testMode = 0;
        String testInput = "7\n" +
                "1 2 1 3 1 2 1\n";
        /*-------------------------------------------------------------------------------------------------------*/
        FastReader in = new FastReader(testMode == 0 ? System.in : new ByteArrayInputStream(testInput.getBytes()));
        PrintWriter out = new PrintWriter(System.out);
        new ProblemSolver().solve(in, out);
        out.close();
    }
}

class ProblemSolver {
    int A[] = new int[300001];
    TreeSet<Integer> B = new TreeSet<>();
    ArrayList<Integer> C = new ArrayList<>();

    void solve(FastReader in, PrintWriter out) {
        int n = in.nextInt();
        for (int i = 0; i < n; i++) A[i] = in.nextInt();
        for (int i = 0; i < n; i++) {
            if (B.contains(A[i])) {
                C.add(i + 1);
                B.clear();
            } else B.add(A[i]);
        }
        if (C.size() == 0) {
            out.println(-1);
            return;
        }
        out.println(C.size());
        int j = 1;
        for (int i = 0; i + 1 < C.size(); i++) {
            int k = C.get(i);
            out.println(j + " " + k);
            j = k + 1;
        }
        out.println(j + " " + n);
    }
}

class Pair implements Comparable<Pair> {
    int a, b;

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

    public int compareTo(Pair o) {
        return 0;
        /*if (this.a < o.a) return -1;
        if (this.a > o.a) return 1;
        if (this.b == o.b) return 0;
        return (int) ((this.b - o.b) / Math.abs(this.b - o.b));               */
    }
}


class FastReader extends BufferedReader {
    private StringTokenizer st;

    public FastReader(InputStream is) {
        super(new InputStreamReader(is));
    }

    public String nextToken() {
        try {
            while (st == null || !st.hasMoreElements()) {
                st = new StringTokenizer(readLine());
            }
            return st.nextToken();
        } catch (IOException e) {
            return null;
        }
    }

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

    public long nextLong() {
        return Long.parseLong(nextToken());
    }

    public int[] nextArrayInt(int size) {
        int[] ret = new int[size];
        for (int i = 0; i < size; i++) {
            ret[i] = nextInt();
        }
        return ret;
    }
}