Extra Element
Contest: Codeforces Round 568 (Div. 2)
Difficulty rating: 1700
Tags: implementation, math

A sequence $$$a_1, a_2, \dots, a_k$$$ is called an arithmetic progression if for each $$$i$$$ from $$$1$$$ to $$$k$$$ elements satisfy the condition $$$a_i = a_1 + c \cdot (i - 1)$$$ for some fixed $$$c$$$.

For example, these five sequences are arithmetic progressions: $$$[5, 7, 9, 11]$$$, $$$[101]$$$, $$$[101, 100, 99]$$$, $$$[13, 97]$$$ and $$$[5, 5, 5, 5, 5]$$$. And these four sequences aren't arithmetic progressions: $$$[3, 1, 2]$$$, $$$[1, 2, 4, 8]$$$, $$$[1, -1, 1, -1]$$$ and $$$[1, 2, 3, 3, 3]$$$.

You are given a sequence of integers $$$b_1, b_2, \dots, b_n$$$. Find any index $$$j$$$ ($$$1 \le j \le n$$$), such that if you delete $$$b_j$$$ from the sequence, you can reorder the remaining $$$n-1$$$ elements, so that you will get an arithmetic progression. If there is no such index, output the number -1.

Input format:
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$) — length of the sequence $$$b$$$. The second line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — elements of the sequence $$$b$$$.

Output format:
Print such index $$$j$$$ ($$$1 \le j \le n$$$), so that if you delete the $$$j$$$-th element from the sequence, you can reorder the remaining elements, so that you will get an arithmetic progression. If there are multiple solutions, you are allowed to print any of them. If there is no such index, print -1.

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

Note:
Note to the first example. If you delete the $$$4$$$-th element, you can get the arithmetic progression $$$[2, 4, 6, 8]$$$.

Note to the second example. The original sequence is already arithmetic progression, so you can delete $$$1$$$-st or last element and you will get an arithmetical progression again.

Example input:
5
2 6 8 7 4

Example output:
4

Example input:
8
1 2 3 4 5 6 7 8

Example output:
1

Editorial:
First of all, we should sort all elements (from smaller to larger, for example, or vice versa). But in the answer is index of element in original sequence, so let's keep the array $$$c$$$ of pairs $$$\{b_i, i\}$$$, sorted by $$$b_i$$$.
Now we need to check some simple cases, for example, let's check the $$$1$$$-st and the $$$2$$$-nd elements whether they are the answers. We'll create the copy of original sequence, but without $$$1$$$-st element. Then we will check that all neighboring elements $$$c_i.first$$$ and $$$c_{i + 1}.first$$$ have the same difference. If it is so, $$$c_1.second$$$ is the answer. For the $$$2$$$-nd element similarly.
Okay, now we have the sequence, where $$$1$$$-st and $$$2$$$-nd elements aren't the answers. Let's fix difference between them $$$d$$$ and check that all neighboring elements $$$c_i.first$$$ and $$$c_{i + 1}.first$$$ have the same difference. If we meet the pair, where the difference doesn't equal $$$d$$$, we will check the difference between $$$c_{i}.first$$$ and $$$c_{i + 2}.first$$$. If it equals $$$d$$$, so $$$c_{i + 1}.second$$$ may be the answer, otherwise there is no answer (output $$$-1$$$). If we will find one else pair, where the difference doesn't equals $$$d$$$, there is no answer too.
If all pairs have the difference that equals $$$d$$$, it means that it's initially arithmetic progression. So we can remove first or last element and get arithmetic progression again. In this case let's output $$$1$$$.