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:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

import java.io.*;
import java.util.*;

/**
 *
 * @author Bryan AW
 */
public class Codeforces {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args){
        
        //Longest k-Good Segment
              
              Scanner sc=new Scanner(System.in);
              
              PrintWriter pw=new PrintWriter(System.out);
              
              int n=Integer.parseInt(sc.next());
              int k=Integer.parseInt(sc.next());
              
              Integer[] a=new Integer[n+1];
              
              for (int i=1;i<=n;i++){
                  a[i]=Integer.parseInt(sc.next());
              }
              
              int l=1, maxL=-1;
              int L=1, R=1, d=0;
              
               HashMap <Integer, Integer> mode
              =new HashMap <Integer, Integer> ();
              
              for (int i=1;i<=n;i++){
                  Integer m=mode.get(a[i]);
                  if (m==null){
                      mode.put(a[i], 1);
                      d++;
                  }
                  else {
                      mode.put(a[i], m+1);
                  }
                  if (d>k) {
                      int sz=i-l;
                      if (maxL<sz){
                          maxL=sz;
                          L=l;
                          R=i-1;
                      }
                      Integer x=mode.get(a[l]);
                      x--;
                      mode.put(a[l], x);
                      if (x==0){
                          mode.put(a[l], null);
                          d--;
                      }
                      l++;
                  }
              }
              
              if (maxL<n-l+1){
                  L=l;
                  R=n;
              } 
              
              pw.printf("%d %d\n", L, R);
              
              pw.close();
        
    }
    
}