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.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
import java.util.TreeSet;

import javax.jws.Oneway;

public class Masked{
	private static int[] permutatation ;
	private static boolean[] used;
	private static int[] binary;
	private static ArrayList<Integer> listString = new ArrayList<Integer>();
	private static HashSet<String> setInteger = new HashSet<String>();

	public static void main(String[] args){
		solveC();
	}
	
	private static void solveC(){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] list = new int[n];
		for(int i = 0 ; i < n ; i++){
			list[i] = scan.nextInt();
		}
		
		ArrayList<Integer> lf = new ArrayList<Integer>();
		TreeSet<Integer> set = new TreeSet<Integer>();
		for(int i = 0 ; i < n ; i ++){
			if(i > 0 && set.contains(list[i])){
				lf.add(i);
				set.clear();
			}else{
				set.add(list[i]);
			}
		}
		
		if(lf.size() == 0 ) System.out.println(-1);
		else{
			PrintWriter pw = new PrintWriter(System.out);
			
			System.out.println(lf.size());
			int f = 1;
			for(int i = 0 ; i < lf.size() ; i++){
				if(i == lf.size()-1){
					pw.printf("%d %d\n",f,n);
					pw.flush();
					return;
				}
				pw.printf("%d %d\n",f,lf.get(i)+1);
				f = lf.get(i)+2;
				pw.flush();
			}
		}
		
	}




	private static class SegmentTree{
		
		
		private int[] tree;
		private int maxSize,height;
		
		
		private final int START = 0;
		private int EndIndex;
		private final int root=0;
	
		private int leftChild(int n){
			return 2*n+1;
		}
		
		private int rightChild(int n){
			return 2*n +2;
		}
		
		private int mid(int a,int b){
			return (a+b)/2;
		}
		
		public SegmentTree(int size){
			height =(int)( Math.ceil(Math.log(size)/Math.log(2)));
			maxSize = 2*(int)Math.pow(2,height)-1;
			tree = new int[maxSize];
			EndIndex = size-1;
		}
		
		
		private int getSum(int startIndex,int endIndex, int queryStart,int queryEnd,int current){
			if(queryStart <= startIndex && queryEnd >= endIndex){
				return tree[current];
			}
			if(endIndex < queryStart || startIndex > queryEnd ) return 0;
			
			int m = mid(startIndex,endIndex);
			
			return getSum(startIndex,m,queryStart,queryEnd,leftChild(current))+
					getSum(m+1,endIndex,queryStart,queryEnd,rightChild(current));
		}
		
		
		private int getSumUntil(int queryStart, int queryEnd){
			if(queryStart < 0 || queryEnd > EndIndex) return -1;
			return getSum(0,EndIndex,queryStart,queryEnd,root);
		}
		
		private int constructing(int[] elements,int start,int end,int current){
			if(start == end){
				tree[current] = elements[start]; 
				return tree[current];
			}
			int m = mid(start,end);
			tree[current] = constructing(elements,start,m,leftChild(current))+
					constructing(elements,m+1,end,rightChild(current));
			return tree[current];
		}
		
		private void ConstructSegmentTree(int[] elements){
			constructing(elements, 0,EndIndex,root);
		}
		
		
		public int[] getTree(){
			return tree;
		}
		
		
	}
	
}