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:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author sarthak
 */

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



public class educationalrnd6_C {

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

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

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
                return "";
            }
        }

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

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

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
static class P {

        private int x, y;

        public P(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int hashCode() {
            return (x * 31) ^ y;
        }

        public boolean equals(Object o) {
            if (o instanceof P) {
                P other = (P) o;
                return (x == other.x && y == other.y);
            }
            return false;
        }
    }
    static ArrayList<P> al=new ArrayList<>();
    public static void main(String[] args){
         
    FastScanner s = new FastScanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    int n=s.nextInt();
    int[] a=new int[n+1];
    for(int i=1;i<=n;i++)
        a[i]=s.nextInt();
    
    int si=1;
    int en=1;
    HashMap<Integer,Integer> m=new HashMap<>();
    //for(int i=1;i<=n;i++)m.put(a[i], 0);
    while(en<=n)
    {
        boolean f=false;
        boolean cT=false;
        while(true&&en<=n){
            int ce=a[en];
            if(!m.containsKey(ce))m.put(ce, 0);
            int c=m.get(ce);
            c++;
            m.put(ce, c);
            if(c==2){
                f=true;
                break;
            }
            en++;
        }
        if(f){
            al.add(new P(si,en));
            si=en+1;
            en++;
            m=new HashMap<>();
        }
    }
    if(al.size()!=0){
    if(al.get(al.size()-1).y!=n){
        P p=al.get(al.size()-1);
        al.set(al.size()-1, new P(p.x,n));
    }
        System.out.println(al.size());

    for(P p:al)
        System.out.println(p.x + " "+ p.y);
    }
    else
        System.out.println(-1);
    
    
    }


}