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:
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main {

    static int n;

    public static void solve() {
        n = IO.readInt();

        int[] first = new int[1000001];
        int[] last = new int[1000001];
        int[] count = new int[1000001];

        for (int index = 1; index <= n; ++index) {
            int a = IO.readInt();
            if (count[a] == 0) {
                first[a] = index;
                last[a] = index;
            }
            else {
                last[a] = index;
            }
            count[a]++;
        }
        int maxIndex = 0;
        for (int index = 1; index <= 1000000; ++index) {
            if (count[index] > count[maxIndex]) {
                maxIndex = index;
            }
            else if (count[index] == count[maxIndex]) {
                if (last[index] - first[index] < last[maxIndex] - first[maxIndex]) {
                    maxIndex = index;
                }
            }
        }
        IO.print(first[maxIndex] + " " + last[maxIndex]);
    }

    // Input/Output ================================
    public static class IO {

        private static Scanner scanner;
        private static PrintWriter writer;

        public static void setUp(InputStream in, OutputStream out) {
            scanner = new Scanner(new java.io.BufferedInputStream(in));
            writer = new PrintWriter(out);
        }

        public static boolean isEmpty() {
            return !scanner.hasNext();
        }

        public static boolean hasNextLine() {
            return scanner.hasNextLine();
        }

        public static String readLine() {
            String line;
            try {
                line = scanner.nextLine();
            } catch (Exception e) {
                line = null;
            }
            return line;
        }

        public static String readString() {
            return scanner.next();
        }

        public static int readInt() {
            return scanner.nextInt();
        }

        public static int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int index = 0; index < n; ++index) {
                a[index] = readInt();
            }
            return a;
        }

        public static double readDouble() {
            return scanner.nextDouble();
        }

        public static float readFloat() {
            return scanner.nextFloat();
        }

        public static long readLong() {
            return scanner.nextLong();
        }

        public static char readChar() {
            return scanner.findInLine("[^\\s]").charAt(0);
        }

        public static void print(Object o) {
            writer.print(o);
            writer.flush();
        }

        public static void println(Object o) {
            writer.println(o);
            writer.flush();
        }
    }

    // Algorithms ================================

    private static class Algo {

        private static int binSearch(int[] array, int n, int lo, int hi) {
            if (lo > hi) {
                return lo;
            }

            int mid = lo + (hi - lo) / 2;
            int cmp = (int) java.lang.Math.signum(n - array[mid]);
            if (cmp < 0) {
                return binSearch(array, n, lo, mid - 1);
            } else if (cmp == 0) {
                return mid;
            } else {
                return binSearch(array, n, mid + 1, hi);
            }
        }

        private static void permutations(int n) {
            int[] p = new int[n];
            for (int index = 0; index < n; ++index) {
                p[index] = index + 1;
            }

            while (true) {
                IO.println(Arrays.toString(p));

                int k = n - 1;
                while (k > 0) {
                    if (p[k] < p[k - 1]) {
                        k--;
                    }
                    else {
                        break;
                    }
                }
                if (k == 0) {
                    break;
                }
                int j = n - 1;
                while (p[j] < p[k - 1]) {
                    j--;
                }

                int t = p[j];
                p[j] = p[k - 1];
                p[k - 1] = t;

                int i = 0;
                while (k + i < n - 1 - i) {
                    t = p[k + i];
                    p[k + i] = p[n - i - 1];
                    p[n - i - 1] = t;
                    i++;
                }
            }
        }

        private static boolean isPrime(int number) {
            if (number <= 1) {
                return false;
            }
            if (number <= 3) {
                return true;
            }
            if (number % 2 == 0 || number % 3 == 0) {
                return false;
            }
            int i = 5;
            while (i * i <= number) {
                if (number % i == 0 || number % (i + 2) == 0) {
                    return false;
                }
                i += 6;
            }
            return true;
        }

        private static boolean isPalindrome(int number) {
            int n = number;
            int reverse = 0;
            while (n > 0) {
                reverse *= 10;
                reverse += (n % 10);
                n /= 10;
            }
            return reverse == number;
        }

        public static int gcd(int a,int b) {
            while (b != 0) {
                int tmp = a % b;
                a = b;
                b = tmp;
            }
            return a;
        }
    }

    private static class Math {

        static long c(int n, int k) {
            if (n == 0 && k == 0) {
                return 1;
            }
            int d = 1000;
            int l = 1000000007;
            long[][] c = new long[d + 1][d + 1];
            for (int i = 1; i <= d; ++i) {
                for (int j = 0; j <= i; ++j) {
                    if (i == j || j == 0) {
                        c[i][j] = 1;
                    }
                    else {
                        c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % l;
                    }
                }
            }
            return c[n][k];
        }
    }

    public static void main(String[] args) {
        IO.setUp(System.in, System.out);
        /*
        try {
            IO.setUp(new FileInputStream("encode.in"), new FileOutputStream("encode.out"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            return;
        }
        */
        solve();
    }
}