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.*;
import java.lang.*;
import java.math.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Main LawrenceXavier = new Main();
        LawrenceXavier.I_Love_My_EEvilCatt();
    }

    BufferedReader jvin = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter jvout = new PrintWriter(System.out);
	
    final int maxN = (int)3E5;

    class tData {
        int a, p;
        tData(int _a, int _p) {
            a = _a;
            p = _p;
        }
        int getA() {
            return a;
        }
        int getP() {
            return p;
        }
    }

    int[] a;
    int[] f, trace;
    int n, m;
    tData[] b;
    int[] last;
    int[] ps;



    public class SortComp implements Comparator<tData> {
        @Override
        public int compare(tData x, tData y) {
            return x.getA()-y.getA();
        }
    }

    public void I_Love_My_EEvilCatt() throws IOException {
        n = Integer.parseInt(jvin.readLine());

        f = new int[n];
        trace = new int[n];
        a = new int[n];
        b = new tData[n];
        last = new int[n];
        ps = new int[n];

        StringTokenizer tok = new StringTokenizer(jvin.readLine());
        n = 0;
        while (tok.hasMoreTokens()) {
            a[n] = Integer.parseInt(tok.nextToken());
            b[n] = new tData(a[n], n);
            ++n;
        }

        Arrays.sort(b, new SortComp());

        a[b[0].getP()] = 0;
        for(int i = 1; i < n; ++i) {
            if (b[i].getA() == b[i-1].getA())
                a[b[i].getP()] = a[b[i-1].getP()];
            else 
                a[b[i].getP()] = a[b[i-1].getP()]+1;
        }

        for(int i = 0; i < n; ++i) {
            ps[i] = -1;
            last[i] = -1;
        }
        ps[a[0]] = 0;
        for(int i = 1; i < n; ++i) {
            last[i] = Math.max(last[i-1], ps[a[i]]);
            ps[a[i]] = i;
            trace[i] = -2;
        }

        for(int i = 0; i < n; ++i) {
            if (last[i] == -1)
                f[i] = -1;
            else if (last[i] == 0 || (last[i] > 0 && f[last[i]-1] < 0)) {
                f[i] = 1;
                trace[i] = -1;
            }
            else {
                f[i] = f[last[i]-1]+1;
                trace[i] = last[i]-1;
            }
        }
        if (f[n-1] <= 0) jvout.print(-1);
        else {
            jvout.println(f[n-1]);
            doTrace(n-1);
        }
        jvout.flush();
    }
    void doTrace(int i) {
        if (i < 0) return;
        doTrace(trace[i]);
        // jvout.println(trace[i]+2 + " " + (i+1));
        jvout.print(trace[i]+2);
        jvout.print(" ");
        jvout.println(i+1);
    }
}