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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.TreeMap;


public class ER6 {
	static int N;
	static int arr[];
	static TreeMap<Integer,Integer> T = new TreeMap();
	static IR in = new IR(System.in);
	static HashSet h = new HashSet();
	static ArrayList<Pair> res = new ArrayList();

	static class Pair{
		int first;
		int last;

		public Pair(int first,int last)
		{
			this.first = first; this.last = last;
		}
	}
	public static void main(String[]args)throws Throwable
	{
		N = in.j();
		arr = new int[N];
		boolean can = false;
		for(int i=0;i<N;i++){
			arr[i] = in.j();
			if(h.contains(arr[i])) can = true;
			h.add(arr[i]);

		}
		h.clear();
		if(!can)
		{
			System.out.println("-1");
			return;
		}
		int twos = 0;

		StringBuilder sb = new StringBuilder();
		int pars = 0;

		int l = 0;
		for(int i=0;i<N;i++)
		{
			Integer last = T.get(arr[i]);
			if(last==null||last==-1)
			{
				T.put(arr[i],i); continue;
			}
			else{
				if(T.get(arr[i])<l) {
					T.put(arr[i],i);
					continue;
				}
				++pars;

				res.add(new Pair(l+1,(i+1)));
				l = i+1;
				T.put(arr[i],-1);
			}


		}
		int len = res.size();
		res.get(len-1).last= N;
		for(int i=0;i<len;i++)
		{
			sb.append(res.get(i).first +" "+res.get(i).last); sb.append("\n");
		}



		System.out.println(pars);
		System.out.print(sb);

	}







	static class IR{
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public IR(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public long ll()
		{
			return Long.parseLong(next());
		}

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


	}
}