Going Home
Contest: Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 1800
Tags: brute force, hashing, implementation, math

It was the third month of remote learning, Nastya got sick of staying at dormitory, so she decided to return to her hometown. In order to make her trip more entertaining, one of Nastya's friend presented her an integer array $$$a$$$.

Several hours after starting her journey home Nastya remembered about the present. To entertain herself she decided to check, are there four different indices $$$x, y, z, w$$$ such that $$$a_x + a_y = a_z + a_w$$$.

Her train has already arrived the destination, but she still hasn't found the answer. Can you help her unravel the mystery?

Input format:
The first line contains the single integer $$$n$$$ ($$$4 \leq n \leq 200\,000$$$) — the size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2.5 \cdot 10^6$$$).

Output format:
Print "YES" if there are such four indices, and "NO" otherwise.

If such indices exist, print these indices $$$x$$$, $$$y$$$, $$$z$$$ and $$$w$$$ ($$$1 \le x, y, z, w \le n$$$).

If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example $$$a_2 + a_3 = 1 + 5 = 2 + 4 = a_1 + a_6$$$. Note that there are other answer, for example, 2 3 4 6.

In the second example, we can't choose four indices. The answer 1 2 2 3 is wrong, because indices should be different, despite that $$$a_1 + a_2 = 1 + 3 = 3 + 1 = a_2 + a_3$$$

Example input:
6
2 1 5 2 7 4

Example output:
YES
2 3 1 6

Example input:
5
1 3 1 9 20

Example output:
NO

Editorial:
Let's prove that if there're at least four different pairs indices with the common sum ($$$a_{x_1} + a_{y_1} = a_{x_2} + a_{y_2} = \ldots = a_{x_4} + a_{y_4}$$$), then there necessarily will be two pairs such that all four indices in them are unique.
Let's analyze some cases:
• There're four pairs of the form $$$(x, y_1), (x, y_2), (x, y_3), (x, y_4)$$$ with sum $$$S$$$. Then $$$a_x + a_{y_1} = a_x + a_{y_2} = a_x + a_{y_3} = a_x + a_{y_4} = S$$$ from which we can conclude that $$$a_{y_1} = a_{y_2} = a_{y_3} = a_{y_4}$$$, and it means that pairs $$$(y_1, y_2)$$$ and $$$(y_3, y_4)$$$ are suitable as answer.
• There're three pairs of the form $$$(x, y_1), (x, y_2), (x, y_3)$$$ and the fourth pair doesn't contain index $$$x$$$. Then whatever the fourth pair $$$(z, w)$$$ is, it necessarily doesn't contain index $$$x$$$ and at least one of indices $$$y_1, y_2, y_3$$$ which means we can take as answer pairs $$$(z, w)$$$ and one of three that contain $$$x$$$.
• Other cases are analyzed in the same way. To make sure that answer always exists among such four pairs, we can imagine graph, where vertices are indices, and there is an edge between two vertices if the corresponding pair of indices has sum $$$S$$$. If such a graph has at least four edges and the degree of all vertices is at most two (we excluded the larger degrees by examining the previous cases), then there will always be two edges with disjoint ends.
How to find answer using this? Let's launch simple $$$\mathcal{O}(n^2)$$$ bruteforce which for every sum will save all found pairs with such sum, and for each pair check if there's another already found pair with the same sum and such indices that all four indices in these two pairs are unique.
Let's notice it works in $$$\mathcal{O}(min(n^2, n + C)$$$, because once for some sum we find the fourth pair, we can immediately print the answer. And if the answer is "NO", then we've done no more than $$$\mathcal{O}(C)$$$ iterations of bruteforce.