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;
	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];
		for (int i = 0; i < n; i++)
			arr[i] = Integer.parseInt(in.next());

		// solve
		solve();
	}

	private void solve()
	{
		count = new int[1000005];
		int r = -1;
		int distinct = 0;
		int ansL = 0;
		int ansSize = 0;

		// for each l keep moving r as much as you can
		for (int l = 0; l < n; l++)
		{
			// keep moving r
			while (r + 1 < n)
			{
				int extra = count[arr[r + 1]] == 0 ? 1 : 0;
				if (distinct + extra > k)
					break;
				else
				{
					distinct += extra;
					count[arr[r + 1]]++;
					r++;
				}
			}

			// minimize
			if (r - l + 1 > ansSize)
			{
				ansSize = r - l + 1;
				ansL = l;
			}

			// remove l
			count[arr[l]]--;
			if (count[arr[l]] == 0)
				distinct--;
		}

		System.out.println((ansL + 1) + " " + (ansL + ansSize - 1 + 1));
	}

}

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();
	}
}