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.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.TreeSet;


public class C {
	
	public static void main(String[] args) throws IOException 
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		
		TreeSet<Integer> set = new TreeSet<Integer>();
		ArrayList<Interval> sol = new ArrayList<Interval>(n>>1);
		int j = 0;
		for(int i = 0; i < n; ++i)
		{
			int x = sc.nextInt();
			if(set.contains(x))
			{
				sol.add(new Interval(j, i));
				j = i + 1;
				set = new TreeSet<Integer>();
			}
			else
				set.add(x);
		}
		if(sol.size() == 0)
			out.println(-1);
		else
		{
			if(j < n)
			{
				Interval lst = sol.get(sol.size() - 1);
				lst.b = n - 1;
			}
			out.println(sol.size());
			for(Interval i: sol)
				out.format("%d %d\n", i.a + 1, i.b + 1);
			
		}
		
		
		out.flush();
		out.close();
		
	}
	
	static class Interval
	{
		int a, b;
		
		Interval(int x, int y)
		{
			a = x;
			b = y;
		}
	}
	
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

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

		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
		
		public double nextDouble() throws IOException
		{
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if(x.charAt(0) == '-')
			{
				neg = true;
				start++;
			}
			for(int i = start; i < x.length(); i++)
				if(x.charAt(i) == '.')
				{
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				}
				else
				{
					sb.append(x.charAt(i));
					if(dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg?-1:1);
		}
		
		public boolean ready() throws IOException {return br.ready();}


	}
}