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
#include <bits/stdc++.h>
using namespace std;
int n, a[1000005], b[1000005], c[1000005], cnt, prime[20000], is[10000005],
    pp[20], num[20], cnt2;
vector<int> G[10000005];
void Get_prime() {
  for (int i = 2; i <= 10000000; i++) {
    if (!is[i]) {
      cnt++;
      prime[cnt] = i;
    }
    for (int j = 1; j <= cnt; j++) {
      if (i * prime[j] > 10000000) break;
      is[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
void dfs(int p, int qq, int val) {
  if (qq == cnt2 + 1) {
    if (G[val].size() < 2) G[val].push_back(b[p]);
    return;
  }
  for (int i = 0; i <= num[qq]; i++) {
    if (i != 0) val *= pp[qq];
    dfs(p, qq + 1, val);
  }
}
int main() {
  Get_prime();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), c[i] = a[i];
  sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; i++) b[i] = a[i];
  for (int i = 1; i <= n; i++) {
    cnt2 = 0;
    for (int j = 1; prime[j] * prime[j] <= a[i]; j++) {
      if (a[i] % prime[j] == 0) {
        ++cnt2;
        pp[cnt2] = prime[j];
        num[cnt2] = 0;
        while (a[i] % prime[j] == 0) {
          a[i] /= prime[j];
          num[cnt2]++;
        }
      }
    }
    if (a[i] > 1) {
      cnt2++;
      pp[cnt2] = a[i];
      num[cnt2] = 1;
    }
    dfs(i, 1, 1);
  }
  int l, r, lans, rans;
  long long ans = (long long)1e15;
  for (int i = 1; i <= 10000000; i++) {
    if (G[i].size() >= 2)
      if (ans > (long long)1 * G[i][0] * G[i][1] / i) {
        ans = (long long)1 * G[i][0] * G[i][1] / i;
        l = G[i][0];
        r = G[i][1];
      }
  }
  for (int i = 1; i <= n; i++) {
    if (c[i] == l) {
      lans = i;
      break;
    }
  }
  for (int i = n; i; i--) {
    if (c[i] == r) {
      rans = i;
      break;
    }
  }
  if (lans > rans) swap(lans, rans);
  printf("%d %d\n", lans, rans);
  return 0;
}
