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:
//package main;

import java.io.*;
import java.util.*;

public final class Main {
    BufferedReader br;
    StringTokenizer stk;
    
    public static void main(String[] args) throws Exception {
        new Main().run();
    }
    
    {
        stk = null;
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    
    long mod = 998244353;
    StringBuilder res = new StringBuilder(1000005);
    void run() throws Exception {
        int n = ni();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = ni();
        }
        
        Stack<Pack> stack = new Stack<>();
        stack.push(new Pack(1, a[0]));
        for(int i = 1; i < n; i++) {
            if(stack.peek().elements.contains(a[i])) {
                stack.peek().end = i + 1;
                if(i == n - 1) {
                    break;
                }
                stack.push(new Pack(i + 2, a[i + 1]));
                i++;
            } else {
                stack.peek().end = i + 1;
                stack.peek().elements.add(a[i]);
            }
        }
        
        if(stack.peek().start == stack.peek().end || stack.peek().end - stack.peek().start + 1 == stack.peek().elements.size()) {
            stack.pop();
        }
        if(stack.isEmpty()) {
            System.out.println("-1\n");
            return;
        }
        if(stack.peek().end != n) {
            stack.peek().end = n;
        }
        if(stack.size() == 1) {
            if(stack.peek().elements.size() == n) {
                res.append("-1\n");
            } else {
                res.append(stack.size()).append("\n");
                res.append(stack.peek()).append("\n");
            }
        } else {
            res.append(stack.size()).append("\n");
            for(Pack pack : stack) {
                res.append(pack).append("\n");
            }
        }
        
        System.out.print(res);
    }
    
    class Pack {
        int start, end;
        HashSet<Integer> elements;
        public Pack(int start, int elem) {
            elements = new HashSet<>();
            elements.add(elem);
            this.start = this.end = start;
        }
        @Override
        public String toString() {
            return start + " " + end;
        }
    }
    
    //Reader & Writer
    String nextToken() throws Exception {
        if (stk == null || !stk.hasMoreTokens())
            stk = new StringTokenizer(br.readLine(), " ");
        return stk.nextToken();
    }

    char[] nc() throws Exception {
        return nextToken().toCharArray();
    }

    int ni() throws Exception {
        return Integer.parseInt(nextToken());
    }

    long nl() throws Exception {
        return Long.parseLong(nextToken());
    }
    
    double nd() throws Exception {
        return Double.parseDouble(nextToken());
    }
    
    //Some Misc methods
    int get(int l, int r, int[] a) {
        return l == 0 ? a[r] : a[r] - a[l - 1];
    }
    
    void shuffle(long[] a) {
        Random r = new Random();
        for(int i = 0; i < a.length; i++) {
            int idx = r.nextInt(a.length);
            long temp = a[i];
            a[i] = a[idx];
            a[idx] = temp;
        }
    }
    
    void reverse(long[] a) {
        for(int i = 0, j = a.length - 1; i < j; i++, j--) {
            long temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}