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
import math
from collections import defaultdict
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = list(map(int, input().split()))

    MAX = 10**7 + 1
    res = MAX * MAX

    #MAX_P = int(math.sqrt(MAX))
    MAX_P = 3163

    primes = []
    p = 2
    sieve = [True] * (MAX_P+1)
    while p < MAX_P:
        if sieve[p]:
            primes.append(p)
            k = 2
            while k * p < MAX_P:
                sieve[k * p] = False
                k += 1
        p += 1

    np = len(primes)
    cand1 = {}
    cand2 = {}
    ind1 = {}
    ind2 = {}

    res = MAX * MAX
    for index in range(n):
        val = a[index]
        if val >= res:
            continue

        divisors = [1]
        p = 0
        while val > 0 and p < np:
            while val % primes[p] == 0:
                divisors += [d * primes[p] for d in divisors]
                val //= primes[p]
            p += 1
        if val > 1:
            divisors += [d * val for d in divisors]

        for d in set(divisors):
            if d not in cand1:
                cand1[d] = a[index]
                ind1[d] = index
            else:
                if d not in cand2:
                    if a[index] < cand1[d]:
                        cand2[d] = cand1[d]
                        ind2[d] = ind1[d]
                        cand1[d] = a[index]
                        ind1[d] = index
                    else:
                        cand2[d] = a[index]
                        ind2[d] = index
                else:
                    if a[index] < cand1[d]:
                        cand2[d] = cand1[d]
                        ind2[d] = ind1[d]
                        cand1[d] = a[index]
                        ind1[d] = index
                    elif a[index] < cand2[d]:
                        cand2[d] = a[index]
                        ind2[d] = index
                    else:
                        continue
                if res > cand1[d] // d * cand2[d]:
                    x, y = ind1[d], ind2[d]
                    res = cand1[d] // d * cand2[d]

    print(min(x+1, y+1), max(x+1, y+1))


if __name__ == '__main__':
    main()
