#P1154G. Minimum Possible LCM
Minimum Possible LCM
No submission language available for this problem.
Description
You are given an array $a$ consisting of $n$ integers $a_1, a_2, \dots, a_n$.
Your problem is to find such pair of indices $i, j$ ($1 \le i < j \le 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).
The first line of the input contains one integer $n$ ($2 \le n \le 10^6$) — the number of elements in $a$.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^7$), where $a_i$ is the $i$-th element of $a$.
Print two integers $i$ and $j$ ($1 \le i < j \le 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.
Input
The first line of the input contains one integer $n$ ($2 \le n \le 10^6$) — the number of elements in $a$.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^7$), where $a_i$ is the $i$-th element of $a$.
Output
Print two integers $i$ and $j$ ($1 \le i < j \le 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.
Samples
5
2 4 8 3 6
1 2
5
5 2 11 3 7
2 4
6
2 5 10 1 10 2
1 4