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:
//package com.competitions.educational.year2016.jantomarch;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.Set;

public final class Q4
{
	static int n, k, arr[], count[];
	static InputReader in;
	static OutputWriter out;
	
	public static void main(String[] args)
	{
		in = new InputReader(System.in);
		out = new OutputWriter(System.out);
		
		//System.out.println(1e6 + 5);
		
		solve3();
		
		out.flush();
		
		in.close();
		out.close();
	}

	static void solve()
	{
		n = in.nextInt();
		k = in.nextInt();
		
		arr = new int[n];
		
		for (int i = 0; i < n; i++)
			arr[i] = in.nextInt();
		
		if (k == 1)
		{
//			System.out.println("hello");
			out.println(1 + " " + 1);
			
			return;
		}
		
		count = new int[(int) 1e6 + 5];
		
		int maxLeft, maxRight, left, right, uniqueCount;
		Set<Integer> set = new HashSet<Integer>();
		
		maxLeft = maxRight = left = right = uniqueCount = 0;
		
		while (right < n)
		{
			if (count[arr[right]] == 0)
			{
				uniqueCount++;
				
				set.add(arr[right]);
			}
			
			System.out.println("increasing count of " + arr[right] + ", previously was : " + count[arr[right]]);
			count[arr[right]]++;
			
			System.out.println("^^left : " + left + ", right : " + right + ", uC : " + uniqueCount);
			
			System.out.println("--------------------------------\nThe count array looks like : ");
			Iterator<Integer> iterator = set.iterator();
			
			while (iterator.hasNext())
			{
				int curr = iterator.next();
				
				System.out.println(curr + " : " + count[curr]);
			}
			
			System.out.println("&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&");
			
			if (uniqueCount == k)
			{
				boolean entered = false;
				
				while (right < n && count[arr[right]] > 0)
				{
					entered = true;
					count[arr[right]]++;
					right++;
					System.out.println("increasing right");
				}
				
				if (entered)
				{
					if (right < n)
					{
						System.out.println("decreasing count of " + arr[right] + ", previously was : " + count[arr[right]]);
						count[arr[right]]--;
					}
					
					right--;
				}
				
				System.out.println("left : " + left + ", right : " + right
						+ ", maxL : " + maxLeft + ", maxR : " + maxRight);
				
				if (right - left > maxRight - maxLeft)
				{
					maxRight = right;
					maxLeft = left;

					System.out.println("**left : " + left + ", right : "
							+ right + ", maxL : " + maxLeft + ", maxR : "
							+ maxRight);
				}
				
				System.out.println("####left : " + left + ", right : " + right + ", uC : " + uniqueCount);
				
				while (left < n && uniqueCount == k)
				{
					count[arr[left]]--;

					if (count[arr[left]] == 0)
						uniqueCount--;

					left++;
					System.out.println("increasing left");
				}
				
				System.out.println("@@left : " + left + ", right : " + right + ", uC : " + uniqueCount);
			}
			
			right++;
		}
		
		right--;
		
		if (right - left > maxRight - maxLeft)
		{
			maxRight = right;
			maxLeft = left;
		}
		
		out.println((maxLeft + 1) + " " + (maxRight + 1));
	}
	
	static void solve2()
	{
		n = in.nextInt();
		k = in.nextInt();
		
		arr = new int[n];
		
		for (int i = 0; i < n; i++)
			arr[i] = in.nextInt();
		
		count = new int[(int) 1e6 + 5];
		
		int currLeft, currRight, maxLeft, maxRight, uniqueCount;
		
		currLeft = currRight = maxLeft = maxRight = uniqueCount = 0;
		
		while (currRight < n)
		{
			System.out.println("currLeft : " + currLeft + ", currRight : "
					+ currRight + ", maxL : " + maxLeft + ", maxR : "
					+ maxRight + ", uC : " + uniqueCount);
			
			if (uniqueCount < k)
			{
				if (count[arr[currRight]] == 0)
					uniqueCount++;
				
				count[arr[currRight]]++;
				
				boolean entered = false;

				while (currRight < n - 1 && count[arr[currRight + 1]] > 0)
				{
					currRight++;
					count[arr[currRight]]++;
					entered = true;
					System.out.println("** currR : " + currRight
							+ ", arr[currRight] : " + arr[currRight]
							+ ", count : " + count[arr[currRight]]);
				}

				if (entered)
				{
					System.out.println("*reducing count of " + arr[currRight]
							+ ", prev. was : " + count[arr[currRight]]);
					count[arr[currRight]]--;
					currRight--;
				}
			}
			else
			{
				while (currLeft < n)
				{
					System.out.println("reducing count of " + arr[currLeft]
							+ ", prev. was : " + count[arr[currLeft]]);
					count[arr[currLeft]]--;
					currLeft++;

					if (count[arr[currLeft - 1]] == 0)
					{
						uniqueCount--;

						break;
					}
				}
			}
			
			if (currRight - currLeft > maxRight - maxLeft)
			{
				System.out.println("changing max, to => left : " + currLeft + ", right : " + currRight + ", uC : " + uniqueCount);
				maxRight = currRight;
				maxLeft = currLeft;
			}
			
			currRight++;
		}
		
		System.out.println("count : ");
		
		for (int i = 0; i < 10; i++)
			System.out.println(i + " : " + count[i]);
		
		out.println((maxLeft + 1) + " " + (maxRight + 1));
	}
	
	static void solve3()
	{
		n = in.nextInt();
		k = in.nextInt();
		
		arr = new int[n];
		
		for (int i = 0; i < n; i++)
			arr[i] = in.nextInt();
		
		count = new int[(int) 1e6 + 5];
		
		int currLeft, currRight, maxLeft, maxRight, uniqueCount;
		
		currLeft = currRight = maxLeft = maxRight = uniqueCount = 0;
		
		for (currRight = 0; currRight < n; currRight++)
		{
			if (uniqueCount < k)
			{
				if (currRight == n)
					break;
				
				if (count[arr[currRight]] == 0)
					uniqueCount++;
				
				count[arr[currRight]]++;
			}
			else
			{
				if (currLeft == n)
					break;
				
				//currRight--;
				
/*				System.out.println("**cL : " + currLeft + ", arr[cL] : "
						+ arr[currLeft] + ", count[arr[cL]] : "
						+ count[arr[currLeft]] + ", uC : " + uniqueCount
						+ ", cR : " + currRight);*/
				
				while (currRight < n && count[arr[currRight]] > 0)
				{
					count[arr[currRight]]++;
					currRight++;
				}
				
				currRight--;
				
				if (currRight - currLeft > maxRight - maxLeft)
				{
//					System.out.println("changing MAX!!");
					
					maxRight = currRight;
					maxLeft = currLeft;
				}

				while (currLeft < n && count[arr[currLeft]] != 0)
				{
//					System.out.println("in loop");
					count[arr[currLeft]]--;
					
					if (count[arr[currLeft]] == 0)
					{
						currLeft++;
						uniqueCount--;
						
						break;
					}

					currLeft++;
				}
			}
			
			if (currRight - currLeft > maxRight - maxLeft)
			{
//				System.out.println("changing MAX!!");
				
				maxRight = currRight;
				maxLeft = currLeft;
			}
			
/*			System.out.println("currL : " + currLeft + ", currR : " + currRight
					+ ", maxL : " + maxLeft + ", maxR : " + maxRight + ", uC : " + uniqueCount);*/
		}
		
/*		System.out.println("0 1 2 3 4 5 6 7 8 9");
		
		for (int i = 0; i < 10; i++)
			System.out.print(count[i] + " ");
		
		System.out.println();*/
		
		out.println((maxLeft + 1) + " " + (maxRight + 1));
	}
	
	static class InputReader
	{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream)
		{
			this.stream = stream;
		}

		public int read()
		{
			if (numChars == -1)
				throw new InputMismatchException();

			if (curChar >= numChars)
			{
				curChar = 0;
				try
				{
					numChars = stream.read(buf);
				}
				catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}

			return buf[curChar++];
		}

		public int nextInt()
		{
			int c = read();

			while (isSpaceChar(c))
				c = read();

			int sgn = 1;

			if (c == '-')
			{
				sgn = -1;
				c = read();
			}

			int res = 0;

			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();

				res *= 10;
				res += c & 15;

				c = read();
			} while (!isSpaceChar(c));

			return res * sgn;
		}
		
		public int[] nextIntArray(int arraySize)
		{
			int array[] = new int[arraySize];
			
			for (int i = 0; i < arraySize; i++)
				array[i] = nextInt();
			
			return array;
		}

		public long nextLong()
		{
			int c = read();

			while (isSpaceChar(c))
				c = read();

			int sign = 1;

			if (c == '-')
			{
				sign = -1;

				c = read();
			}

			long result = 0;

			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();

				result *= 10;
				result += c & 15;

				c = read();
			} while (!isSpaceChar(c));

			return result * sign;
		}
		
		public long[] nextLongArray(int arraySize)
		{
			long array[] = new long[arraySize];
			
			for (int i = 0; i < arraySize; i++)
				array[i] = nextLong();
			
			return array;
		}

		public float nextFloat() // problematic
		{
			float result, div;
			byte c;

			result = 0;
			div = 1;
			c = (byte) read();

			while (c <= ' ')
				c = (byte) read();

			boolean isNegative = (c == '-');

			if (isNegative)
				c = (byte) read();

			do
			{
				result = result * 10 + c - '0';
			} while ((c = (byte) read()) >= '0' && c <= '9');

			if (c == '.')
				while ((c = (byte) read()) >= '0' && c <= '9')
					result += (c - '0') / (div *= 10);

			if (isNegative)
				return -result;

			return result;
		}

		public double nextDouble() // not completely accurate
		{
			double ret = 0, div = 1;
			byte c = (byte) read();

			while (c <= ' ')
				c = (byte) read();

			boolean neg = (c == '-');

			if (neg)
				c = (byte) read();

			do
			{
				ret = ret * 10 + c - '0';
			} while ((c = (byte) read()) >= '0' && c <= '9');

			if (c == '.')
				while ((c = (byte) read()) >= '0' && c <= '9')
					ret += (c - '0') / (div *= 10);

			if (neg)
				return -ret;

			return ret;
		}

		public String next()
		{
			int c = read();

			while (isSpaceChar(c))
				c = read();

			StringBuilder res = new StringBuilder();

			do
			{
				res.appendCodePoint(c);

				c = read();
			} while (!isSpaceChar(c));

			return res.toString();
		}

		public boolean isSpaceChar(int c)
		{
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
		
		public String nextLine()
		{
			int c = read();
			
			StringBuilder result = new StringBuilder();
			
			do
			{
				result.appendCodePoint(c);
				
				c = read();
			} while (!isNewLine(c));
			
			return result.toString();
		}
		
		public boolean isNewLine(int c)
		{
			return c == '\n';
		}

		public void close()
		{
			try
			{
				stream.close();
			}
			catch (IOException e)
			{
				e.printStackTrace();
			}
		}

	}

	static class OutputWriter
	{
		private PrintWriter writer;

		public OutputWriter(OutputStream stream)
		{
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
					stream)));
		}

		public OutputWriter(Writer writer)
		{
			this.writer = new PrintWriter(writer);
		}

		public void println(int x)
		{
			writer.println(x);
		}

		public void print(int x)
		{
			writer.print(x);
		}

		public void println(int array[], int size)
		{
			for (int i = 0; i < size; i++)
				println(array[i]);
		}

		public void print(int array[], int size)
		{
			for (int i = 0; i < size; i++)
				print(array[i] + " ");
		}

		public void println(long x)
		{
			writer.println(x);
		}

		public void print(long x)
		{
			writer.print(x);
		}

		public void println(long array[], int size)
		{
			for (int i = 0; i < size; i++)
				println(array[i]);
		}

		public void print(long array[], int size)
		{
			for (int i = 0; i < size; i++)
				print(array[i]);
		}

		public void println(float num)
		{
			writer.println(num);
		}

		public void print(float num)
		{
			writer.print(num);
		}

		public void println(double num)
		{
			writer.println(num);
		}

		public void print(double num)
		{
			writer.print(num);
		}

		public void println(String s)
		{
			writer.println(s);
		}

		public void print(String s)
		{
			writer.print(s);
		}

		public void println()
		{
			writer.println();
		}

		public void printSpace()
		{
			writer.print(" ");
		}

		public void flush()
		{
			writer.flush();
		}

		public void close()
		{
			writer.close();
		}

	}

}

/*

13 3
1 2 1 4 3 4 1 3 2 4 2 3 2

70 3
402220 282419 650495 930659 650495 889316 305186 305186 402220 889316 282419 305186 402220 650495 930659 650495 624910 650495 305186 574693 889316 201793 201793 930659 156713 305186 624910 574693 402220 402220 305186 930659 650495 889316 650495 889316 402220 156713 624910 402220 889316 650495 305186 305186 650495 305186 201793 650495 624910 201793 282419 650495 930659 574693 402220 930659 889316 624910 930659 650495 402220 574693 201793 282419 624910 402220 201793 650495 624910 650495 402220

*/