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 + 10;
int n, a[maxn], b[maxn] = {0};
int main() {
  ios::sync_with_stdio(false);
  int i, j, k, max1 = 0;
  cin >> n;
  for (i = 1; i <= n; i++) {
    cin >> a[i];
    b[a[i]]++;
    max1 = max(max1, a[i]);
  }
  long long l, r, min1 = 1e15;
  for (i = 1; i <= max1; i++) {
    vector<long long> v;
    for (j = i; j <= max1; j += i) {
      if (!b[j]) continue;
      for (k = 0; k < min(2, b[j]); k++) v.push_back(j);
      if (v.size() >= 2) break;
    }
    if (v.size() >= 2) {
      long long sum = v[0] / i * v[1];
      if (sum < min1) min1 = sum, l = v[0], r = v[1];
    }
  }
  for (i = 1; i <= n; i++) {
    if (a[i] == l) {
      l = i;
      break;
    }
  }
  for (i = 1; i <= n; i++) {
    if (a[i] == r && i != l) {
      r = i;
      break;
    }
  }
  if (l > r) swap(l, r);
  cout << l << " " << r << endl;
}
