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 urtbest;
import java.awt.Point;
import java.io.*;
import java.io.ObjectInputStream.GetField;
import java.math.MathContext;
import java.util.*;
import java.util.jar.Attributes.Name;
import java.util.logging.Level;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



















import javax.swing.text.MaskFormatter;
 
 
 
 
 
 
 
public class TestClass {
 
static long mod ;
static char[][] A;
static int[][] Ans;
static Point[][] Pa;
static int[][] V;


public static void google(int x , int y , int px , int py){
	
	 V[x][y]=1;
	 Pa[x][y] = new Point(px,py);
	 LinkedList<Point> Q  = new LinkedList<Point>();
	 int o=1;
	 int[] X = {1,-1,0,0};
	 int[] Y = {0,0,1,-1};
	 Q.add(new Point(x,y));
	 while(!Q.isEmpty()){
		 
		  x = Q.peek().x;
		  y =Q.peek().y;
		  Q.pop();
		  Pa[x][y] = new Point(px,py);
		  
		  for(int i=0;i<4;i++){
			  
			  int dx = x + X[i];
			  int dy = y+Y[i];
			  
		if(dx>=0 && dy>=0 && dx<A.length && dy<A[0].length && A[dx][dy]!='*' && V[dx][dy]!=1){
			    o++;
			    V[dx][dy]=1;
			    Q.add(new Point(dx,dy));
		}
		  }
		 
	 }
	// System.out.println(px+" "+py+" "+o);
	 Ans[px][py]=o;
	
}

public static void main(String args[] ) throws java.lang.Exception {
 
 
 
InputStream inputStream = System.in;
InputReader in = new InputReader(inputStream);
 
//BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//BufferedReader in = new BufferedReader(new FileReader("C:\\Users\\Sompathak\\Desktop\\yes.txt"));
//Scanner in = new Scanner(new FileReader("C:\\Users\\Sompathak\\Desktop\\yes.txt"));
// PrintWriter pw = new PrintWriter(new FileWriter("C:\\Users\\Sompathak\\Desktop\\output.java"));
//InputStream inputStream = System.in;
//InputReader in = new InputReader(inputStream);
//Scanner in = new Scanner(new InputStreamReader(System.in));
//Scanner in = new Scanner(new FileReader("C:\\Users\\Sompathak\\Desktop\\yes.java"));
//we can we will ??? !!!!!! SOM RISES
//long startTime = System.currentTimeMillis();
//long startTime = System.currentTimeMillis();
mod = (long)Math.pow(10,9)+7;
int n = in.nextInt();
int k= in.nextInt();
int[] A = new int[n];
for(int i=0;i<n;i++) A[i]=in.nextInt();
int[] F = new int[1000003];
int l=1;
int r=1;
int len =0;
int start=0;
F[A[0]]++;
int o=1;
for(int i=1;i<n;i++){
	
	  if(F[A[i]]==0) o++;
	    F[A[i]]++;
	   while(o>k && start<=i){
		   if(F[A[start]]==1) o--;
		   F[A[start]]--;
		   start++;
	   }
	   
	   if(len<i-start){
		   len = i-start;
		   l=i+1;
		   r=start+1;
	   }
}
System.out.println(r+" "+l);

//System.out.println(totalTime+" sec....."+" "+startTime+" "+endTime); 
  
  
 
 
}public static class InputReader
{
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
 
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 - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
 
public String readString()
{
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 double readDouble() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
double res = 0;
while (!isSpaceChar(c) && c != '.') {
if (c == 'e' || c == 'E')
return res * Math.pow(10, nextInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
}
if (c == '.') {
c = read();
double m = 1;
while (!isSpaceChar(c)) {
if (c == 'e' || c == 'E')
return res * Math.pow(10, nextInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
m /= 10;
res += (c - '0') * m;
c = read();
}
}
return res * sgn;
}
public long readLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c)
{
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
 
public String next()
{
return readString();
}
 
public interface SpaceCharFilter
{
public boolean isSpaceChar(int ch);
}
}
}