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:
 //    package com.company;
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.lang.reflect.Array;
    import java.sql.SQLOutput;
    import java.util.*;
    public class Main {

        public static void main(String[] args) throws IOException {
            Scanner s = new Scanner(System.in);
            //BufferedReader s=new BufferedReader(new InputStreamReader(System.in));
             StringBuilder sb1 = new StringBuilder();//int n=Integer.parseInt(s.readLine());
         int n=s.nextInt();
         int k=s.nextInt();
         long[] a=new long[n];
         for(int i=0;i<n;i++){
             a[i]=s.nextLong();
         }
          int st=0;int end=0;int []count=new int[1000001];
         int c=0;
         int max=0;int fst=0;int fend=0;
         for(int i=0;i<n;i++){
             if(count[(int)a[i]]==0&&c==k){
               while(count[(int)a[st]]!=0){
                 count[(int )a[st]]--;
                 if(count[(int) a[st]]==0) {st++;break;}
                 st++;}
             }
             if(count[(int)a[i]]==0&&c<k) c++;

             count[(int) a[i]]++;
            if(i-st+1>max){
                max=i-st+1;fend=i;fst=st;
            }
         }       if(n-1-st+1>max){
                max=n-1-st+1;fend=n-1;fst=st;
            }
            System.out.println((fst+1)+" "+(fend+1));
        }static long ans=0;static long count=0;
        static void dfs(int i,ArrayList<Integer>[] adj,int[] vis,int [] vtime,int time,int n){
            vis[i]=1;
            vtime[time]++;
            if(adj[i]==null){return;}
            for(Integer j:adj[i]){
                if(vis[j]==0){
                     dfs(j,adj,vis,vtime,time+1,n);
                }
            }}
        static  void computeLPSArray(String pat, int M, int lps[])
        {
            int len = 0;
            int i = 1;
            lps[0] = 0;
            while (i < M) {
                if (pat.charAt(i) == pat.charAt(len)) {
                    len++;
                    lps[i] = len;
                    i++;
                }
                else // (pat[i] != pat[len])
                {
                    if (len != 0) {
                        len = lps[len - 1];
                    }
                    else // if (len == 0)
                    {
                        lps[i] = len;
                        i++;
                    }
                }
            }
        }
        static boolean isPrime(int n)
        {
            if (n <= 1) return false;
            if (n <= 3) return true;

            if (n % 2 == 0 || n % 3 == 0) return false;

            for (int i = 5; i * i <= n; i = i + 6)
                if (n % i == 0 || n % (i + 2) == 0)
                    return false;

            return true;
        }

        static double power(double x, long y, int p) {
            double res = 1;
            x = x % p;
            while (y > 0) {
                if ((y & 1) == 1)
                    res = (res * x) % p;
                y = y >> 1;
                x = (x * x) % p;
            }
            return res;
        }
        public static void fracion(double x) {
            String a = "" + x;
            String spilts[] = a.split("\\."); // split using decimal
            int b = spilts[1].length(); // find the decimal length
            int denominator = (int) Math.pow(10, b); // calculate the denominator
            int numerator = (int) (x * denominator); // calculate the nerumrator Ex
            // 1.2*10 = 12
            int gcd = (int)gcd((long)numerator, denominator); // Find the greatest common
            // divisor bw them
            String fraction = "" + numerator / gcd + "/" + denominator / gcd;
            // System.out.println((denominator/gcd));
            long x1=modInverse(denominator / gcd,998244353  );
            //  System.out.println(x1);
            System.out.println((((numerator / gcd )%998244353 *(x1%998244353  ))%998244353  ) );
        }static int anst=Integer.MAX_VALUE;
      static StringBuilder sb1=new StringBuilder();
        public static int bfs(int i1, ArrayList<Integer>[] h, int[] vis, int n,int val1) {
            Queue<Integer> q = new LinkedList<Integer>();
            q.add(i1);Queue<Integer> aq=new LinkedList<Integer>();
            aq.add(0);
            while(!q.isEmpty()){
                int i=q.poll();
                int val=aq.poll();
                if(i==n){
                    return val;
                }
                if(h[i]!=null){
                    for(Integer j:h[i]){
                       if(vis[j]==0){
                        q.add(j);vis[j]=1;
                           aq.add(val+1);}
                    }
                }
            }return -1;
        }
        static int i(String a) {
            return Integer.parseInt(a);
        }
        static long l(String a) {
            return Long.parseLong(a);
        }
        static String[] inp() throws IOException {
            BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
            return s.readLine().trim().split("\\s+");
        }


        static long gcd(long a, long b) {
            if (b == 0)
                return a;
            return gcd(b, a % b);
        }
        static long modInverse(int a, int m)
        {


            {
                // If a and m are relatively prime, then modulo inverse
                // is a^(m-2) mode m
                return (power(a, m - 2, m));
            }
        }

        // To compute x^y under modulo m
        static long power(int x, int y, int m)
        {
            if (y == 0)
                return 1;

            long p = power(x, y / 2, m) % m;
            p = (p * p) % m;

            if (y % 2 == 0)
                return p;
            else
                return (x * p) % m;
        }

        // Function to return gcd of a and b

    }
    class Student
    {
        int l;int r;
        public Student(int l, int r) {
            this.l = l;
            this.r = r;
        }
        // Constructor


        // Used to print student details in main()
        public String toString()
        {
            return this.l+" ";
        }
    }

    class Sortbyroll implements Comparator<Student>
    {
        // Used for sorting in ascending order of
        // roll number
        public int compare(Student a, Student b){
            return a.l-b.l;  }
    } class Sortbyroll1 implements Comparator<Student>
    {
        // Used for sorting in ascending order of
        // roll number
        public int compare(Student a, Student b){
           if(a.r==b.r) return a.l-b.l;
            return a.r-b.r;
        }
    }