You are given an array a consisting of n integers a_1, a_2, ..., a_n.

Your problem is to find such pair of indices i, j (1 ≤ i < j ≤ n) that lcm(a_i, a_j) is minimum possible.

lcm(x, y) is the least common multiple of x and y (minimum positive number such that both x and y are divisors of this number).

Input

The first line of the input contains one integer n (2 ≤ n ≤ 10^6) — the number of elements in a.

The second line of the input contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^7), where a_i is the i-th element of a.

Output

Print two integers i and j (1 ≤ i < j ≤ n) such that the value of lcm(a_i, a_j) is minimum among all valid pairs i, j. If there are multiple answers, you can print any.

Examples

Input


5
2 4 8 3 6


Output


1 2


Input


5
5 2 11 3 7


Output


2 4


Input


6
2 5 10 1 10 2


Output


1 4
import java.util.*;
import java.io.*;

public class MinimumPossibleLCM {
    static ArrayList<Integer> primes;
    static Pair[] mins;
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int N = scanner.nextInt();
        int[] elts = new int[N];
        int max =0;
        for(int i = 0; i < N; i++) {
            elts[i] = scanner.nextInt();
            max = Math.max(max, elts[i]);
        }
        int[] sieve = buildSieve(max+1);
        mins = new Pair[max+1];
        for(int i = 0; i <= max; i++) {
            mins[i] = new Pair(-1, -1);
        }
        Pair[] vals = new Pair[N];
        for(int i =0; i < N; i++) vals[i] = new Pair(elts[i], i);
        Arrays.sort(vals);
        for(int i = 0; i < N; i++) {
            if (i > 1 && vals[i].f == vals[i-2].f) continue;
            int val = vals[i].f;
            ArrayList<Pair> divs = new ArrayList<>(20);
            while(val > 1) {
                int d = sieve[val];
                if (!divs.isEmpty() && divs.get(divs.size()-1).f == d) divs.get(divs.size()-1).s++;
                else divs.add(new Pair(d, 1));
                val/=d;
            }
            rec(0,1,vals[i].s, divs);
        }
        long min = Long.MAX_VALUE;
        int ansI = -1;
        int ansJ = -1;
        for(int i = 1; i <= max; i++) {
            Pair idxs = mins[i];
            if (idxs.s == -1) continue;
            long cur = (long)elts[idxs.f]*((long)elts[idxs.s]/(long)i);
            if (min > cur) {
                min = cur;
                ansI = Math.min(idxs.f+1, idxs.s+1);
                ansJ = Math.max(idxs.s+1, idxs.f+1);
            }
        }
        out.println(ansI + " " + ansJ);
        out.flush();
    }
    
    public static void rec(int pos, int curd, int idx, ArrayList<Pair> divs) {
        if (pos == divs.size()) {
            if (mins[curd].f == -1) mins[curd].f = idx;
            else if (mins[curd].s == -1) mins[curd].s = idx;
        }
        else {
            int curm = 1;
            for(int i = 0; i <= divs.get(pos).s; i++) {
                rec(pos + 1, curd * curm,idx, divs);
                curm *= divs.get(pos).f;
            }
        }
    }
    
    public static class Pair implements Comparable<Pair> {
        int f,s;
        public Pair(int ff, int ss) {
            f = ff; s= ss;
        }
        public int compareTo(Pair o) {
            if (this.f == o.f) return Integer.compare(this.s, o.s);
            return Integer.compare(this.f, o.f);
        }
    }
    
    //Returns both the list of primes
    //as well as stores (for each number) the smallest number that divides us.
    public static int[] buildSieve(int N) {
        int[] ret = new int[N];
        primes = new ArrayList<>(1000);
        ret[0] = ret[1] = 1;
        for(int i = 2; i < N; i++) {
            if (ret[i] == 0) {
                primes.add(i);
                ret[i] = i;
            }
            for(int j = 0; j < primes.size() && primes.get(j) <= ret[i] && (long)i * (long)primes.get(j) < (long)N; j++) {
                ret[i*primes.get(j)] = primes.get(j);
            }
        }
        return ret;
    }
    
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}
