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 Main {
	static final int M = 1000000007;

	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long[] readArrayLong(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		int[] readArrayInt(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() {return Double.parseDouble(next());}
	}

	// sorting template
	static void sortLong(long[] a) {
		ArrayList<Long> l = new ArrayList<>();
		for (long i : a)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < a.length; i++)
			a[i] = l.get(i);
	}

	static void sortInt(int[] a) {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i : a)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < a.length; i++)
			a[i] = l.get(i);
	}

	static class Graph {
		private ArrayList<Integer> adj[];
		public String s;
		public String dpch;

		Graph(int n) {
			adj = new ArrayList[n + 1];
			for (int i = 1; i <= n; i++) {
				adj[i] = new ArrayList<>();
			}
		}

		void addEdges(int u, int v) {
			adj[u].add(v);
			adj[v].add(u);
		}

		void dfs(int v, boolean[] vis) {
			vis[v] = true;
			for (int u : adj[v]) {
				if (!vis[u]) {
					dfs(u, vis);
				}
			}
		}

		int bfs(int v, boolean[] vis, int[] ans) {
			int sum = 0;
			Queue<Integer> q = new LinkedList<>();
			q.add(v);
			vis[v] = true;
			ans[v] = 0;
			while (q.size() > 0) {
				int node = q.poll();
				for (int u : adj[node]) {
					if (!vis[u]) {
						vis[u] = true;
						ans[u] = ans[node] + 1;
						q.add(u);
					}
				}
			}
			return sum;
		}
	}

	static class Pair<F, S> {
		F first;
		S second;

		Pair(F first, S second) {
			this.first = first;
			this.second = second;
		}

		public F getFirst() {
			return this.first;
		}

		public S getSecond() {
			return this.second;
		}
		// Sort on basis of first term, reverse p1.first and p2.first to sort in desc
		// Collections.sort(a, (p1, p2) -> (p1.first - p2.first));

		// Sort on the basis of second term, reverse p1.second and p2.second to sort
		// in
		// desc
		// Collections.sort(a, (p1, p2) -> (p1.second - p2.second));
	}

	static int __gcd(int a, int b) {
		if (b == 0)
			return a;
		return __gcd(b, a % b);
	}

	public static int subtree, maxNode, maxDist;
	public static int[] dist;
	public static int[] connected;

	public static void main(String[] args) throws IOException {
		FastScanner fs = new FastScanner();
		int t = 1;
		StringBuffer res = new StringBuffer();
		for (int tt = 1; tt <= t; tt++) {
			int n = fs.nextInt();
			int k = fs.nextInt();
			int[] a = fs.readArrayInt(n);
			int i = 0, j = 0, max = 0, c= 0 , d = 0;
			int[] hash = new int[1000001];
			Set<Integer> s = new HashSet<>();
			for(;i<n&&j<n;){
				if(s.size()>k){
					if (hash[a[j]] == 1) {
						s.remove(a[j]);
					}
					hash[a[j]]--;
					j++;
				}else{
					if(i-j>max){
						c = j+1;
						d = i;
						max =i - j;
					}
					hash[a[i]]++;
					s.add(a[i]);
					i++;
				}
			}
			if(s.size()<=k){
				if(i-j>max){
					c = j+1;
					d = i;
				}
			}
			res.append(c+" "+d);
		}
		System.out.println(res);
	}
	private static boolean condition(int mid, int n, int[] a, int k, int[] pre) {
		int max = Integer.MAX_VALUE;
		for(int i=0,j=mid;i<n&&j<=n;i++,j++){
			max = Math.min(pre[j]-pre[i], max);
		}
		return max>=k;
	}
}