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.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main
{

	/* IO */
	InputReader in;
	StringTokenizer tok;
	StringBuilder ans;

	/* FIELDS */
	int n, k, right;
	int[] arr, count;

	public static void main(String[] args) throws FileNotFoundException
	{
		Main sol = new Main();
		sol.begin();

	}

	private void begin() throws FileNotFoundException
	{
		// io
		boolean file = false;
		if (file)
			in = new InputReader(new FileInputStream("input.txt"));
		else
			in = new InputReader(System.in);
		ans = new StringBuilder();

		// read
		n = Integer.parseInt(in.next());
		k = Integer.parseInt(in.next());
		arr = new int[n];
		count = new int[1000005];
		for (int i = 0; i < n; i++)
			arr[i] = Integer.parseInt(in.next());
		
		// solve
		solve();
	}

	private void solve()
	{
		// binary search for the answer
		int l = 0;
		int r = n;
		while(r - l > 3)
		{
			int mid = (l + r) / 2;
			if (valid(mid)) 
				l = mid;
			else
				r = mid - 1;
		}
		for (int i = r; i >= l; i--) 
			if (valid(i)) 
			{
				System.out.println((right - i + 1) + " " + right);
				return;
			}
			

	}

	private boolean valid(int x)
	{
		// take the first x values
		Arrays.fill(count, 0);
		int distinct = 0;
		for (int i = 0; i < x; i++)
		{
			if (count[arr[i]] == 0)
				distinct++;
			count[arr[i]]++;
		}
		if (distinct <= k)
		{
			right = x;
			return true;
		}

		// move that segment
		for (int i = x; i < n; i++)
		{
			if (count[arr[i]] == 0)
				distinct++;
			count[arr[i]]++;
			count[arr[i - x]]--;
			if (count[arr[i - x]] == 0)
				distinct--;
			if (distinct <= k)
			{
				right = i + 1;
				return true;
			}
		}

		return false;
	}
}

class InputReader
{
	BufferedReader reader;
	StringTokenizer tok;

	public InputReader(InputStream stream)
	{
		reader = new BufferedReader(new InputStreamReader(stream), 32768);
		tok = new StringTokenizer("");
	}

	public String next()
	{
		while (!tok.hasMoreTokens())
			try
			{
				tok = new StringTokenizer(reader.readLine());
			} catch (IOException e)
			{
				e.printStackTrace();
			}
		return tok.nextToken();
	}
}