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.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
	
//	private static StreamTokenizer inputReader = new StreamTokenizer(
//			new BufferedReader(new InputStreamReader(System.in)));
//	
	
	Scanner in = new Scanner(System.in);
	
	static java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));

//	public static int nextInt() {
//		int a = -1;
//		try {
//			inputReader.nextToken();
//			a = (int) inputReader.nval;
//		} catch (Exception e) {
//		}
//		return a;
//	}

	public static void main(String[] args) throws IOException {
		int numberOfItems = Integer.parseInt(reader.readLine());
		String[] strings = reader.readLine().split(" ");
		int[] numbers = new int[numberOfItems];
		
		for (int i = 0; i < numberOfItems; i++) {
			numbers[i] = Integer.parseInt(strings[i]);
		}
		
		Set<Integer> set = new TreeSet<>();
		
		
		StringBuilder builder = new StringBuilder();
		List<StartEnd> list = new ArrayList(200000); 
		
		int answer = 0;
		int start = 1;
		for (int i = 0; i < numberOfItems; i++) {
			if (set.contains(numbers[i])) {
				answer++;
				set = new HashSet<>();
				list.add(new StartEnd(start, i + 1));
				start = i + 2;
			} else {
				set.add(numbers[i]);
			}
		}
		
		if (answer > 0) {
			StartEnd last = list.get(list.size() - 1);
			
			if (last.end < numberOfItems) {
				last.end = numberOfItems;
			}
			
			System.out.println(answer);
			
			for (int i = 0; i < list.size(); i++) {
				builder.append(list.get(i).start + " ");
				builder.append(list.get(i).end + "\n");
			}
			
			System.out.println(builder);
		} else {
			System.out.println(-1);
		}
	}
	
	private static class StartEnd {
		int start;
		int end;
		
		public StartEnd(int start, int end) {
			this.start = start;
			this.end = end;
		}
	}

}