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;
const int maxn = 1e7 + 5;
int n;
int a[maxn], minn[maxn][2], ansl[maxn], ansr[maxn];
bool vis[maxn];
vector<int> pr;
vector<pair<int, int>> v;
void init() {
  for (int i = 2; i < maxn; i++) {
    if (!vis[i]) pr.push_back(i);
    for (int j = 0; j < pr.size() && pr[j] * i < maxn; j++) {
      if (i % pr[j] == 0) break;
      vis[i * pr[j]] = true;
    }
  }
  for (int i = 0; i < maxn; i++) minn[i][0] = minn[i][1] = INT32_MAX;
}
void add(int d, int idx) {
  int &val = a[idx];
  if (val < minn[d][1]) {
    minn[d][0] = minn[d][1];
    minn[d][1] = val;
    ansl[d] = ansr[d];
    ansr[d] = idx;
  } else {
    if (val < minn[d][0]) {
      minn[d][0] = val;
      ansl[d] = idx;
    }
  }
}
void dfs(int pos, int cur, int idx) {
  if (pos == v.size()) {
    add(cur, idx);
  } else {
    int temp = 1;
    for (int i = 0; i <= v[pos].second; i++) {
      dfs(pos + 1, cur * temp, idx);
      temp *= v[pos].first;
    }
  }
}
void work(int idx) {
  int val = a[idx];
  v.clear();
  for (int i = 0; i < pr.size() && pr[i] * pr[i] <= val; i++) {
    if (val % pr[i] == 0) {
      v.push_back({pr[i], 1});
      val /= pr[i];
      while (val % pr[i] == 0) {
        v.back().second++;
        val /= pr[i];
      }
    }
  }
  if (val > 1) {
    v.push_back({val, 1});
  }
  dfs(0, 1, idx);
}
int main() {
  init();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), work(i);
  long long ans = LLONG_MAX;
  int ansp = 1;
  for (int i = 1; i < maxn; i++) {
    if (minn[i][0] == INT32_MAX || minn[i][1] == INT32_MAX) continue;
    if (ans > 1LL * minn[i][0] * minn[i][1] / i) {
      ans = 1LL * minn[i][0] * minn[i][1] / i;
      ansp = i;
    }
  }
  if (ansl[ansp] > ansr[ansp]) swap(ansl[ansp], ansr[ansp]);
  printf("%d %d\n", ansl[ansp], ansr[ansp]);
  return 0;
}
