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.io.*;
import java.util.*;

public class CF1154G {
	static final int A = 10000000;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] aa = new int[n];
		int[] kk = new int[A + 1];
		for (int i = 0; i < n; i++) {
			int a = Integer.parseInt(st.nextToken());
			aa[i] = a;
			kk[a]++;
		}
		int[] x1 = new int[A + 1];
		int[] x2 = new int[A + 1];
		Arrays.fill(x1, A + 1);
		Arrays.fill(x2, A + 1);
		for (int a = 1; a <= A; a++)
			for (int b = a; b <= A; b += a)
				if (kk[b] > 0) {
					int k = Math.min(2, kk[b]);
					int x = b / a;
					while (k-- > 0)
						if (x1[a] > x) {
							x2[a] = x1[a]; x1[a] = x;
						} else if (x2[a] > x)
							x2[a] = x;
				}
		long lcm = (long) (A + 1) * (A + 1);
		int gcd = 0;
		for (int a = A; a >= 1; a--)
			if (x2[a] != A + 1) {
				long x = (long) a * x1[a] * x2[a];
				if (lcm > x) {
					lcm = x;
					gcd = a;
				}
			}
		int a1 = A + 1, a2 = A + 1;
		int i1 = -1, i2 = -1;
		for (int i = 0; i < n; i++) {
			int a = aa[i];
			if (a % gcd == 0) {
				if (a1 > a) {
					a2 = a1; a1 = a;
					i2 = i1; i1 = i;
				} else if (a2 > a) {
					a2 = a;
					i2 = i;
				}
			}
		}
		if (i1 > i2) {
			int tmp = i1; i1 = i2; i2 = tmp;
		}
		i1++; i2++;
		System.out.println(i1 + " " + i2);
	}
}
