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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Problem2 {

    private static final boolean SUBMIT = true;
    private final BufferedReader in;
    private final PrintWriter out;
    private StringTokenizer tokenizer;

    private Problem2(BufferedReader in, PrintWriter out) {
        this.in = in;
        this.out = out;
        this.tokenizer = new StringTokenizer("");
    }

    private static Problem2 createProblem() {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        return new Problem2(in, out);
    }

    public static void main(String[] args) {
        try {
            Problem2 solution = createProblem();
            if (SUBMIT) {
                solution.solve();
            } else {
                solution.solveMany();
            }
            solution.close();
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    public void solveMany() throws Exception {
        int n = readInt();
        for (int i = 0; i < n; i++) {
            timeSolve();
        }
    }

    public void timeSolve() throws Exception {
        long currentTimeMillis = System.currentTimeMillis();
        solve();
        out.flush();
        double timeTaken = System.currentTimeMillis() - currentTimeMillis;
        out.println("time taken: " + timeTaken / 1000);
        out.println("");
    }

    private String readString() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(in.readLine());
        }
        return tokenizer.nextToken();
    }

    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    private void close() throws IOException {
        in.close();
        out.close();
    }

    private void solve() throws Exception {
        int n = readInt();
        int maxCount = 0;
        int max = 0;
        int[] begin = new int[1000001];
        int[] end = new int[1000001];
        int[] count = new int[1000001];
        end[0] = 100000;
        for (int i = 1; i <= n; i++) {
            int cur = readInt();
            if (begin[cur] == 0) {
                begin[cur] = i;
            }
            end[cur] = i;
            count[cur] += 1;
            if (count[cur] > maxCount || (count[cur] == maxCount && end[cur] - begin[cur] < end[max] - begin[max])) {
                maxCount = count[cur];
                max = cur;
            }
        }
        out.print(begin[max] + " " + end[max]);
    }

}