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 PearlsInARow {
 
  public static void main(String[] args) {
    try{
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String input = br.readLine();
      int noOfPearls = Integer.parseInt(input);
      
      String sequence = br.readLine();
      String[] seqArray = sequence.split("\\s+");
      
      Hashtable<String, Integer> recorder = new Hashtable<String, Integer>();
      
      //Solution variables
      int noOfSeq = 0;
      ArrayList<String> listOfSeq = new ArrayList<String>();
      
      int startingLoc = 0;
      for(int i = startingLoc; i < noOfPearls; i++) {
        //Stop if found matching pearls
        if(recorder.containsKey(seqArray[i])) {
          recorder.clear();
          noOfSeq++;
          String ans = (startingLoc + 1) + " " + (i + 1);
          listOfSeq.add(ans);
          //New starting location
          startingLoc = i+1;
        }else{
          recorder.put(seqArray[i], i);
        }
      }
      
      //Don't ignore remaining pearls! Add them to last good seg.
      if(!recorder.isEmpty() && listOfSeq.size() > 0) {
        //Modify last entry
        String[] lastInput = listOfSeq.get(listOfSeq.size() - 1).split("\\s+");
        listOfSeq.remove(listOfSeq.size() - 1);
        listOfSeq.add(lastInput[0] + " " + noOfPearls);
      }
      
      PrintWriter pw = new PrintWriter(System.out);
      
      if(noOfSeq == 0) {
        noOfSeq = -1;
      }
      
      pw.println(noOfSeq);
      for(String answer : listOfSeq) {
        pw.println(answer);
      }
      
      isr.close();
      br.close();
      pw.close();
      
    }catch(Exception e) {
      //Ignore
    }
  }
  
  
  
  
  
  
  
  
  
  
}