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
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""Codeforces Round #552 (Div. 3)

Problem G. Minimum Possible LCM

:author:         Kitchen Tong
:mail:    kctong529@gmail.com

Please feel free to contact me if you have any question
regarding the implementation below.
"""

__version__ = '3.4'
__date__ = '2019-04-17'

import sys


def find_minimum_lcm(n, integers):
    already_seen = [0] * (10000001)
    repeated_value = 10000001 * 10000001
    repeated_indices = None
    for index, value in enumerate(integers):
        if already_seen[value]:
            if value < repeated_value:
                repeated_value = value
                repeated_indices = (index, already_seen[value]-1)
        else:
            already_seen[value] = index + 1
    # the smallest repeated integers is our baseline
    answer_value = repeated_value
    answer_indices = repeated_indices
    sorted_integers = sorted(integers)
    min_1, min_2 = sorted_integers[:2]
    if min_1 == min_2:
        return sorted(repeated_indices)
    else:
        factor_lcm = min_1 * min_2
        if factor_lcm < answer_value:
            answer_value = factor_lcm
            answer_indices = (already_seen[min_1]-1,
                              already_seen[min_2]-1)
    for factor in range(2, 10000001):
        if factor > answer_value:
            break
        seen_once = -1
        # have a larger start, so we won't waste time on
        # non-existing small multiples
        for multiple in range(max(1, min_1 // factor) * factor,
                              10000001,
                              factor):
            if already_seen[multiple]:
                if seen_once > 0:
                    factor_lcm = seen_once * multiple // factor
                    if factor_lcm < answer_value:
                        answer_value = factor_lcm
                        answer_indices = (already_seen[seen_once] - 1,
                                          already_seen[multiple] - 1)
                    break
                else:
                    seen_once = multiple
    return sorted(answer_indices)

def main(argv=None):
    n = int(input())
    integers = list(map(int, input().split()))
    i, j = find_minimum_lcm(n, integers)
    print('{0} {1}'.format(i+1, j+1))
    return 0


if __name__ == "__main__":
    STATUS = main()
    sys.exit(STATUS)

