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.InputStreamReader;
import java.util.HashMap;
import java.util.ArrayList;

public class Main
{
	public static void main(String[] args)
	throws Exception
	{
		BufferedReader reader = new BufferedReader(
			new InputStreamReader(System.in)
		);

		int n = Integer.parseInt(reader.readLine());
		String []arr = reader.readLine().split(" ");

		HashMap<Integer,ArrayList<Integer>> indexes = 
			new HashMap<Integer,ArrayList<Integer>>();
		HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>();

		int v,stInd,count,freqV;
		StringBuilder ans = new StringBuilder();
		count = 0;
		stInd = 1;

		for (int i=1;i <= n;++i)
		{
			v = Integer.parseInt(arr[i - 1]);

			if (freq.get(v) instanceof Integer)
			{
				freqV = freq.get(v);
				++freqV;

				if (freqV == 2)
				{
					++count;

					ans.append(stInd);
					ans.append(" ");
					ans.append(i);
					ans.append("\n");

					stInd = i + 1;

					freq.clear();
					indexes.clear();

				}
				else
				{
					ArrayList<Integer> temp = indexes.get(v);
					temp.add(i);
					indexes.put(v,temp);
					freq.put(v,freqV);

				}


			}
			else
			{
				ArrayList<Integer> temp = new ArrayList<Integer>();
				temp.add(i);
				indexes.put(v,temp);
				freq.put(v,1);
			}


		}

		if (count > 0)
		{
			System.out.println(count);

			if (stInd != n + 1)
			{
				System.out.print(ans.substring(0,ans.lastIndexOf(" ") + 1));
				System.out.println(n);
			}
			else
			{
				System.out.println(ans.toString());
			}
		}
		else
		{
			System.out.print(-1);
		}


	}
}