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.*;
	
	public class C620
	{
		public static void main(String[] args)
		{
			InputReader in = new InputReader(System.in);
			PrintWriter pw = new PrintWriter(System.out);
			
			int n = in.nextInt();
			HashSet<Integer> hs = new HashSet<>();
			ArrayList<Integer> left = new ArrayList<>();
			ArrayList<Integer> right = new ArrayList<>();
			int l=0;
			
			for(int i=0;i<n;i++)
			{
				int a = in.nextInt();
				
				if(hs.contains(a))
				{
					left.add(l+1);
					right.add(i+1);
					l = i+1;
					hs.clear();
				}
				else
					hs.add(a);
			}
			
			if(!hs.isEmpty() && !right.isEmpty())
			{
				int r = right.remove(right.size()-1);
				right.add(r+hs.size());
			}
			
			int size = left.size();
			
			if(size==0)
				pw.println(-1);
			else
			{
				pw.println(size);
				
				for(int i=0;i<left.size();i++)
					pw.println(left.get(i)+" "+right.get(i));	
			}
			
			pw.flush();
			pw.close();
		}
	
		
		static class InputReader 
		{
			 
			private final InputStream stream;
			private final byte[] buf = new byte[8192];
			private int curChar, snumChars;
			private SpaceCharFilter filter;
	 
			public InputReader(InputStream stream) 
			{
				this.stream = stream;
			}
	 
			public int snext() 
			{
				if (snumChars == -1)
					throw new InputMismatchException();
				if (curChar >= snumChars) 
				{
					curChar = 0;
					try 
					{
						snumChars = stream.read(buf);
					} 
					catch (IOException e) 
					{
						throw new InputMismatchException();
					}
					if (snumChars <= 0)
						return -1;
				}
				return buf[curChar++];
			}
	 
			public int nextInt() 
		    {
				int c = snext();
				while (isSpaceChar(c)) 
				{
					c = snext();
				}
				int sgn = 1;
				if (c == '-')
			    {
					sgn = -1;
					c = snext();
				}
				int res = 0;
				do 
				{
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					res *= 10;
					res += c - '0';
					c = snext();
				} while (!isSpaceChar(c));
				return res * sgn;
			}
	 
			public long nextLong()
		    {
				int c = snext();
				while (isSpaceChar(c)) 
				{
					c = snext();
				}
				int sgn = 1;
				if (c == '-') 
				{
					sgn = -1;
					c = snext();
				}
				long res = 0;
				do 
				{
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					res *= 10;
					res += c - '0';
					c = snext();
				} while (!isSpaceChar(c));
				return res * sgn;
			}
	 
			public int[] nextIntArray(int n) 
			{
				int a[] = new int[n];
				for (int i = 0; i < n; i++) 
				{
					a[i] = nextInt();
				}
				return a;
			}
	 
			public String readString()
		    {
				int c = snext();
				while (isSpaceChar(c)) 
				{
					c = snext();
				}
				StringBuilder res = new StringBuilder();
				do 
				{
					res.appendCodePoint(c);
					c = snext();
				} while (!isSpaceChar(c));
				return res.toString();
			}
	 
			public String nextLine() 
			{
				int c = snext();
				while (isSpaceChar(c))
					c = snext();
				StringBuilder res = new StringBuilder();
				do 
				{
					res.appendCodePoint(c);
					c = snext();
				} while (!isEndOfLine(c));
				return res.toString();
			}
	 
			public boolean isSpaceChar(int c) 
			{
				if (filter != null)
					return filter.isSpaceChar(c);
				return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
			}
	 
			private boolean isEndOfLine(int c) 
			{
				return c == '\n' || c == '\r' || c == -1;
			}
	 
			public interface SpaceCharFilter
		    {
				public boolean isSpaceChar(int ch);
			}
		}
		
		/*static class CodeX {
        public static void sort(long arr[]) {
            merge_sort(arr, 0, arr.length - 1);
        }

        private static void merge_sort(long A[], long start, long end) {
            if (start < end) {
                long mid = (start + end) / 2;
                merge_sort(A, start, mid);
                merge_sort(A, mid + 1, end);
                merge(A, start, mid, end);
            }

        }

        private static void merge(long A[], long start,long mid, long end) {
            long p = start, q = mid + 1;
            long Arr[] = new long[(int)(end - start + 1)];
            long k = 0;

            for (int i = (int)start; i <= end; i++) {
                if (p > mid)
                    Arr[(int)k++] = A[(int)q++];

                else if (q > end)
                    Arr[(int)k++] = A[(int)p++];

                else if (A[(int)p] < A[(int)q])
                    Arr[(int)k++] = A[(int)p++];

                else
                    Arr[(int)k++] = A[(int)q++];
            }
            for (int i = 0; i < k; i++) {
                A[(int)start++] = Arr[i];
            }

        }

    }*/
	}