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 vis[maxn];
int n;
template <class T>
void read(T &x) {
  bool f = 0;
  char ch = getchar();
  x = 0;
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') f = 1;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  if (f) x = -x;
}
int pos[maxn];
int main() {
  read(n);
  int a;
  int Max = 0;
  long long ans = 1e14;
  int ans1 = 0, ans2 = 0;
  for (int i = 1; i <= n; ++i) {
    read(a);
    if (!vis[a]) {
      pos[a] = i;
    } else {
      if (a < ans) {
        ans1 = pos[a], ans2 = i;
        ans = a;
      }
    }
    ++vis[a], Max = max(Max, a);
  }
  for (int i = 1; i <= Max; ++i) {
    int s1 = 0, s2 = 0;
    for (int j = i; j <= Max; j += i) {
      if (vis[j] && (!s1))
        s1 = j;
      else if (vis[j] && (!s2)) {
        s2 = j;
        long long res = 1LL * s1 / i * s2;
        if (res < ans) {
          ans = res;
          ans1 = pos[s1];
          ans2 = pos[s2];
        }
        break;
      }
    }
  }
  if (ans1 > ans2) swap(ans1, ans2);
  printf("%d %d\n", ans1, ans2);
  return 0;
}
