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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    int []kum;
    int []x;
    int n, k;
    int left, right;
    
    public void add(int val, int pos){
     while (pos <= n){
      kum[pos] += val;   
      pos = pos + (pos & (-pos));
     }
    }
    
    public int sum(int pos){
     int Sum = 0;
      while (pos > 0){
        Sum += kum[pos];  
        pos = pos - (pos & (-pos));
      }
     return Sum;
    }
    
    public int Find(int pos){
     int found = -1;    
     int ll, rr, mid;
     ll = 1;
     rr = pos;
     
     while (ll <= rr){
       mid = (ll + rr) / 2;
       int cur = sum(pos) - sum(mid-1);
       if (cur > k) ll = mid + 1;
       else if (cur <= k){
         rr = mid - 1;
         if (pos - mid > found) found = pos - mid;
       }
     }
      
     return found;
    }
    
    public void solve() throws IOException{
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); 
      String[] s = in.readLine().split(" ");
      n = Integer.parseInt(s[0]);
      k = Integer.parseInt(s[1]);
      
      s = in.readLine().split(" ");
      kum = new int[n+1];
      x = new int[1000001];
      int a;
      int best = -1;
      
      for (int i=0; i<n; i++){
       a = Integer.parseInt(s[i]);
       if (x[a] != 0){
         add(-1, x[a]);
       }
       x[a] = i+1;
       add(1, x[a]);
    
       a = Find(i+1);
       if (a > best){
         best = a;
         left = i+1-a;
         right = i+1;
       }
      }
      System.out.println((left) + " " + (right));
      in.close();
    }
    
    public static void main(String[] args) throws IOException {
      new Main().solve();
    }

}