Problem: Amr has got a large array of size n. Amr doesn't like large arrays so he intends to make it smaller.

Amr doesn't care about anything in the array except the beauty of it. The beauty of the array is defined to be the maximum number of times that some number occurs in this array. He wants to choose the smallest subsegment of this array such that the beauty of it will be the same as the original array.

Help Amr by choosing the smallest subsegment possible.

Input

The first line contains one number n (1 ≤ n ≤ 105), the size of the array.

The second line contains n integers ai (1 ≤ ai ≤ 106), representing elements of the array.

Output

Output two integers l, r (1 ≤ l ≤ r ≤ n), the beginning and the end of the subsegment chosen respectively.

If there are several possible answers you may output any of them. 

Examples

Input

5
1 1 2 2 1


Output

1 5

Input

5
1 2 2 3 1


Output

2 3

Input

6
1 2 2 1 1 2


Output

1 5

Note

A subsegment B of an array A from l to r is an array of size r - l + 1 where Bi = Al + i - 1 for all 1 ≤ i ≤ r - l + 1

Solution (in JAVA):

Solution:
// All important imports
 
import static java.lang.System.in;

import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.GregorianCalendar;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import java.util.Queue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.Vector;
public class Main{

    public static void solve(){
        int n=ni();
        int arr[][]=new int[1000001][3];
        for(int i=0;i<1000001;i++){
            arr[i][0]=0;
            arr[i][1]=0;
            arr[i][2]=0;
            
        }
        for(int i=0;i<n;i++){
            int in = ni();
            arr[in][0]++;
            arr[in][2]=i;
            if(arr[in][0]==1)arr[in][1]=i;
        }
        Arrays.sort(arr,new java.util.Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                int x =Integer.compare(a[0], b[0]);
                x*=-1;
                if(x==0)x = Integer.compare(a[2]-a[1], b[2]-b[1]);
                return x;
            }
        });
        
 out.println((arr[0][1]+1)+" "+(1+arr[0][2]));
            }
    
        // END OF SOLUTION
        // INPUT OUTPUT TEMPLATE
        static String TESTCASES;
        static PrintWriter out;
    public static void main(String[] args) throws Exception,IOException{
                out=new PrintWriter(System.out);
                InputStream myinp=System.in;
                init(myinp);
//                int t=ni();
//                while(t-->0)
                {solve();}
                out.close();
                
                  }
        
    
        static InputStream is;
        static BufferedReader brr;
        static int BUFFER_SIZE = 65000;
        static DataInputStream din;
        static byte[] buffer;
        static int bufferPointer, bytesRead;
        public static void init(InputStream input) {
        is=input;
        brr=new BufferedReader(new InputStreamReader(input));
        din = new DataInputStream(in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
        }
        
    
    protected static byte[] inbuf = new byte[1024];
    static int lenbuf = 0, ptrbuf = 0;
    
        static byte read() throws Exception
        {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }
        
    protected static int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
        
        protected static String readline() throws IOException
        {
            return brr.readLine();
        }
                
    
    
    // extras
    protected static double nd() { return Double.parseDouble(ns()); }
    protected static char nc() { return (char)skip(); }
    protected static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    protected static int skip() { 
            int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; 
        }
        static void fillBuffer() throws Exception
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
        }
        
    protected static String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    protected static char[] nca(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    
    protected static int[] nia(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
        
        protected static int[][] niaindex(int n)
        {
                int ea[][]=new int[n][2];
                for(int i=0;i<n;i++)
                {
                    ea[i][0]=ni();
                    ea[i][1]=i;
                }
                return ea;
        }
        
        protected static long[] nla(int n)
    {
        long[] a = new long[n];
        for(int i = 0;i < n;i++)a[i] = nl();
        return a;
    }
        
        protected static long[][] nlaindex(int n)
        {
                long ea[][]=new long[n][2];
                for(int i=0;i<n;i++)
                {
                    ea[i][0]=ni();
                    ea[i][1]=i;
                }
                return ea;
        }
        
        protected static String[] nsa(int n)
    {
        String[] a = new String[n];
        for(int i = 0;i < n;i++)a[i] = ns();
        return a;
    }
        
        protected static double[] nda(int n)
    {
        double[] a = new double[n];
        for(int i = 0;i < n;i++)a[i] = nd();
        return a;
    }
    
        static int ni2() throws Exception
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = c == '-';
            if (neg) c = read();
            do
            {
                ret = ret * 10 + c - '0';
                c = read();
            } while (c > ' ');
            if (neg) return -ret;
            return ret;
 
        }
        
        
 
    
        
    protected static int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
        
    
    protected static long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
        
        
        // Outputs
        public static void pln(){out.println();}
        public static void ps(String s){out.print(s);}
        public static void pi(int s){out.print(s);}
        public static void pl(long s){out.print(s);}
        public static void pd(double s){out.print(s);}
        public static void psp(){out.print(" ");}
        public static void parr(int s[]){out.println(Arrays.toString(s));}
        public static void parr(String s[]){out.println(Arrays.toString(s));}
        public static void parr(long s[]){out.println(Arrays.toString(s));}        
        public static void parr2(int s[][]){for(int i=0;i<s.length;i++)out.println(Arrays.toString(s[i]));}
        public static void parr2(long s[][]){for(int i=0;i<s.length;i++)out.println(Arrays.toString(s[i]));}
        public static void parr2(String s[][]){for(int i=0;i<s.length;i++)out.println(Arrays.toString(s[i]));}
 
}