Egor Has a Problem

Time limit1sMemory limit1024 MB

Summary

Given a sorted array of distinct positive integers up to 1e18, find indices i<j<p<q with a_i * a_q = a_j * a_p, or report NO.

Level: Hard9 of 10
Topics: Array, Hash map, Math
Solved: No attempts yet

Statement

Egor has come up with a hard problem for a training camp! Here it is:

Given an array $a$ of $n$ positive integers sorted in increasing order, find 4 indices $i < j < p < q$ such that $a_i \cdot a_q = a_j \cdot a_p$ .

He then wrote the checker to this problem:

bool getAnswer(InStream &stream, vector<long long> a) {
    string s = stream.readToken("NO|YES"); // PE if the string is not NO or YES
    if (s == "NO") return false;
    vector<int> b = stream.readInts(4, 1, (int)a.size()); // 4 indices between 1 and n
    int i = b[0] - 1, j = b[1] - 1, p = b[2] - 1, q = b[3] - 1;  // -1 to make 0-indexed
    stream.ensuref(i < j && j < p && p < q, "4 indices should be in increasing order");
    stream.ensuref(a[q] / a[p] == a[j] / a[i], "the products are not equal");
    return true;
}

The multiplication overflows long long, so Egor used division instead. Now Egor might have another problem.

Input

The first line contains one integer $n$ ( $4 \le n \le 500\,000$ ), the size of the array.

The second line contains the array $a_1, a_2, \ldots, a_n$ ( $1 \le a_1 < a_2 < \ldots < a_n \le 10^{18}$ ).

Output

On the first line print "YES" if there is a solution, and "NO" otherwise.

If a solution exists, print the 4 chosen indices in order $i, j, p, q$ , separated by spaces. If there is more than one solution, you can print any one.

Examples4

Example 1
Input
```
6
2 6 11 21 47 120
```
Expected output
```
YES
1 3 4 6
```
Example 2
Input
```
5
1 2 6 30 210
```
Expected output
```
NO
```
Example 3
Input
```
4
7 13 77 143
```
Expected output
```
YES
1 2 3 4
```
Example 4
Input
```
4
10 29 31 100
```
Expected output
```
NO
```