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.util.*;
import java.io.*;

public class Main {
	
	public static void main(String args[]){
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long n = 0;
		long arr[] = null;
		try {
			n = Integer.parseInt(br.readLine());
			String num[] = br.readLine().split(" ");
			arr = new long[(int) n];
			for(long i=0;i<n;i++)
				arr[(int) i] = Long.parseLong(num[(int) i]);
		}catch(Exception e){
			e.printStackTrace();
		}
		long c=0;
		long pos=1;
		int flag=0;
		PrintWriter p = new PrintWriter(System.out);
		HashMap<Long,Long> s = new HashMap<Long,Long>();
		Vector<Long> vec = new Vector<Long>();
		for(long i=0;i<n;i++){
			if(!s.containsKey(arr[(int) i])){
				s.put(arr[(int) i], i+1);
				flag=1;
			}
			else{
				vec.add(pos);
				vec.add(i+1);
				s.clear();
				c++;
				pos = i+2;
				flag=0;
			}
		}
		if(flag==1&&vec.size()!=0){
			vec.remove(vec.size()-1);
			vec.add(n);
		}
		long x=1;
		if(c==0){
			p.println("-1");
			p.flush();
		}
		else{
			p.println(c);
			Iterator it = vec.iterator();
			while(it.hasNext()){
				if(x%2!=0){
					p.print(it.next()+" ");
					p.flush();
				}
				else{
					p.println(it.next());
					p.flush();
				}
				x++;
			}
		}
	}
}