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.sql.Array;
public class B 
{
    public static void main(String[] args)
    {
        new B().solve();
    }

    FasterScanner in=new FasterScanner();
    PrintWriter out=new PrintWriter(System.out);

    public void solve()
    {
        int n=in.nextInt();
        int k=in.nextInt();
        int[] arr=new int[(int)1e6+1];
        int dif=0;
        int l=0;
        int[] v=in.nextIntArray(n);
        int x=v[0];
        arr[x]++;
        dif=1;
        int ans=1;
        int al=0,ar=0;
        for(int i=1;i<n;i++)
        {
            x=v[i];
            arr[x]++;
            if(arr[x]==1)
                dif++;
            if(dif>k)
            {
                while(dif>k)
                {
                    arr[v[l]]--;
                    if(arr[v[l]]==0)
                    {
                        dif--;
                    }
                    l++;
                }
            }
            if(i-l+1>ans)
            {
                ans=i-l+1;
                al=l;
                ar=i;
            }
        }
        out.println((al+1)+" "+(ar+1));
        out.close();
    }
    
    String rev(String s)
    {
        StringBuilder sb=new StringBuilder();
        for(int i=s.length()-1;i>=0;i--)
            sb.append(s.charAt(i));
        return sb.toString();
    }

    class segTree
    {
        
        int n;  // array size
        long t[];

        public segTree(long[] arr)
        {
            t=new long[arr.length*3];
            n=arr.length;
            for(int i=0;i<arr.length;i++)
                t[i+n]=arr[i];
            build();
        }
        
        void build() {  // build the tree
          for (int i = n - 1; i > 0; --i) t[i] = Math.min(t[i<<1] , t[i<<1|1]);
        }

        void modify(int p, long value) {  // set value at position p
          for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = Math.min(t[p] , t[p^1]);
        }

        long query(int l, int r) {  // sum on interval [l, r)
          long res = Integer.MAX_VALUE;
          for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if ((l&1)!=0) res = Math.min(t[l++],res);
            if ((r&1)!=0) res = Math.min(t[--r],res);
          }
          return res;
        }
    }

    class s implements Comparable

    {
        int time;
        int floor;
        public s(int t,int f)
        {
            this.time=t;
            this.floor=f;
        }

        @Override
        public int compareTo(s o) {
            // TODO Auto-generated method stub
            if(this.floor!=o.floor)
                return Integer.compare(this.floor, o.floor);
            else
                return Integer.compare(this.time, o.time);
        }
    }

    public static class FasterScanner {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = System.in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }
        private boolean isEndOfLine(int c) {
            return c=='\n' || c=='\r' || c==-1;
        }
        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        private boolean isSpaceChar(int c) {
            return c=='\n' || c=='\r' || c==-1 || c==' ' || c=='\t';
        }
        public long nextLong() {
            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 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 double nextDouble()
        {
            return Double.parseDouble(nextString());
        }
        public int[] nextIntArray(int n)
        {
            int[] arr=new int[n];
            for(int i=0;i<n;i++)
            {
                arr[i]=nextInt();
            }
            return arr;
        }
        public long[] nextLongArray(int n)
        {
            long[] arr=new long[n];
            for(int i=0;i<n;i++)
            {
                arr[i]=nextLong();
            }
            return arr;
        }
        public int[] nextIntArray10(int n)
        {
            int[] arr=new int[n+1];
            for(int i=1;i<=n;i++)
            {
                arr[i]=nextInt();
            }
            return arr;
        }
        public long[] nextLongArray10(int n)
        {
            long[] arr=new long[n+1];
            for(int i=1;i<=n;i++)
            {
                arr[i]=nextLong();
            }
            return arr;
        }
        public int[] nextIntArray11(int n)
        {
            int[] arr=new int[n+2];
            for(int i=1;i<=n;i++)
            {
                arr[i]=nextInt();
            }
            return arr;
        }
        public long[] nextLongArray11(int n)
        {
            long[] arr=new long[n+2];
            for(int i=1;i<=n;i++)
            {
                arr[i]=nextLong();
            }
            return arr;
        }
    }

}