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.*;
import java.math.*;

public class BasicJava 
{
   
   public static void main(String[] args)
   {
      Task Main = new Task();
      
      Main.solve();
   }
   
   public static class Task
   {
      InputReader in = new InputReader(System.in);
      PrintWriter out = new PrintWriter(System.out);
      
      public class date
      {
         int x, y;
         
      }
      
      public void solve()
      {
         int n = in.nextInt();
         
         int[] t = new int[300010];
         
         date[] v = new date[300010];
         
         HashSet<Integer> set = new HashSet<Integer>();
         
         for (int i = 1; i <= n; i++) t[i] = in.nextInt();
         
         int nrIntervals = 0;
         int last = 0;
         
         for (int i = 1; i <= n; i++) {
            
            if (set.contains(t[i])) {
               
               nrIntervals++;
               
               v[nrIntervals] = new date();
               
               v[nrIntervals].x = last + 1;
               v[nrIntervals].y = i;
               
               last = i;
               
               set.clear();
               
               continue;
            }
            
            set.add(t[i]);
            
         }
         
         if (nrIntervals > 0) {
            
            if (last != n) v[nrIntervals].y = n;
            
         }
         
         if (nrIntervals == 0) {
            
            out.println(-1);
            
            out.close();
            System.exit(0);
            
         }
         
         out.println(nrIntervals);
         
         for (int i = 1; i <= nrIntervals; i++) out.println(v[i].x + " " + v[i].y);
         
         out.close();
         
      }
   }

   static class InputReader
   {
      private InputStream stream;
      private byte[] buf = new byte[2048];
      private int curChar;
      private int numChars;
 
      public InputReader(InputStream stream)
      {
         this.stream = stream;
      }
 
      public int read()
      {
         if (numChars == -1)
            throw new UnknownError();
         if (curChar >= numChars)
         {
            curChar = 0;
            try
            {
               numChars = stream.read(buf);
            }
            catch (IOException e)
            {
               throw new UnknownError();
            }
            if (numChars <= 0)
               return -1;
         }
         return buf[curChar++];
      }
 
      public int peek()
      {
         if (numChars == -1)
            return -1;
         if (curChar >= numChars)
         {
            curChar = 0;
            try
            {
               numChars = stream.read(buf);
            }
            catch (IOException e)
            {
               return -1;
            }
            if (numChars <= 0)
               return -1;
         }
         return buf[curChar];
      }
 
      public void skip(int x)
      {
         while (x-- > 0)
            read();
      }
 
      public int nextInt()
      {
         return Integer.parseInt(next());
      }
 
      public long nextLong()
      {
         return Long.parseLong(next());
      }
 
      public String nextString()
      {
         return next();
      }
 
      public String next()
      {
         int c = read();
         while (isSpaceChar(c))
            c = read();
         StringBuffer res = new StringBuffer();
         do
         {
            res.appendCodePoint(c);
            c = read();
         }
         while (!isSpaceChar(c));
 
         return res.toString();
      }
 
      public String nextLine()
      {
         StringBuffer buf = new StringBuffer();
         int c = read();
         while (c != '\n' && c != -1)
         {
            if (c != '\r')
               buf.appendCodePoint(c);
            c = read();
         }
         return buf.toString();
      }
 
      public double nextDouble()
      {
         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 boolean hasNext()
      {
         int value;
         while (isSpaceChar(value = peek()) && value != -1)
            read();
         return value != -1;
      }
 
      private boolean isSpaceChar(int c)
      {
         return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
   }
}