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 M = 1000001;
int arr[M];
const int N = 10000000;
int lp[N + 1];
int dp[N + 1];
int idp[N + 1];
vector<int> pr;
void seive() {
  for (int i = 2; i <= N; ++i) {
    if (lp[i] == 0) {
      lp[i] = i;
      pr.push_back(i);
    }
    for (int j = 0; j < (int)pr.size() && pr[j] <= lp[i] && i * pr[j] <= N; ++j)
      lp[i * pr[j]] = pr[j];
  }
}
vector<pair<int, int> > primes;
long long ele;
int curr;
long long ans = 1LL * 1e18;
int x, y;
void solve(int pos, int val) {
  if (pos == primes.size()) {
    if (dp[val]) {
      if (ans > ele * dp[val]) {
        ans = ele * dp[val];
        y = curr;
        x = idp[val];
      }
      if (dp[val] > ele / val) {
        dp[val] = ele / val;
        idp[val] = curr;
      }
    } else {
      dp[val] = ele / val;
      idp[val] = curr;
    }
    return;
  }
  for (int i = 0; i <= primes[pos].second; i++) {
    solve(pos + 1, val);
    val *= primes[pos].first;
  }
  return;
}
int main() {
  seive();
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  map<int, int> mp;
  for (int i = 0; i < n; i++) cin >> arr[i];
  for (int i = 0; i < n; i++) {
    if (mp.count(arr[i]) && mp[arr[i]] >= 2) continue;
    mp[arr[i]]++;
    ele = arr[i];
    curr = i;
    primes.clear();
    while (arr[i] != 1) {
      int a_ = lp[arr[i]];
      int cnt = 0;
      while (arr[i] % a_ == 0) {
        cnt++;
        arr[i] /= a_;
      }
      primes.push_back({a_, cnt});
    }
    solve(0, 1);
  }
  cout << x + 1 << " " << y + 1 << '\n';
  return 0;
}
