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.*;
import java.math.*;
public class test {
	public static void main(String args[])
	{
		InputReader in = new InputReader(System.in);
		OutputStream outputStream = System.out;
		PrintWriter out = new PrintWriter(outputStream);
		int n=in.nextInt();
		int k=in.nextInt(),i,count=0;
		int arr[]=new int[n];
		int arr1[]=new int[1000001];
		Arrays.fill(arr1,0);
		for(i=0;i<n;i++)
		{
			arr[i]=in.nextInt();
		}
		int r=0,l=0,lm=0,rm=n-1,max=0;
		while(r<n)
		{
			if(arr1[arr[r]]==0&&count==k)
			{
				arr1[arr[r]]++;
				if(r-l>max)
				{
					max=r-l;
					lm=l;
					rm=r-1;
				}
				while(l<r)
				{
					arr1[arr[l]]--;
					if(arr1[arr[l]]==0)
					{
						l++;
						r++;
						break;
					}
					else
						l++;
				}
			}
			else if(arr1[arr[r]]==0)
			{
				count++;
				arr1[arr[r]]++;
				r++;
			}
			else
			{
				arr1[arr[r]]++;
				r++;
			}
		}
		if(r-l>max)
		{
			lm=l;
			rm=r-1;
		}
		out.println((lm+1)+" "+(rm+1));
		out.close();
	}
	
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream inputstream) {
			reader = new BufferedReader(new InputStreamReader(inputstream));
			tokenizer = null;
		}

		public String nextLine(){
			String fullLine=null;
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					fullLine=reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				return fullLine;
			}
			return fullLine;
		}
		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 nextLong() {
			return Long.parseLong(next());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}