CF1185D.Extra Element

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.

一个序列 $a_1, a_2, \dots, a_k$ 被称为等差数列，当且仅当对每个从 $1$ 到 $k$ 的 $i$，其元素均满足条件 $a_i = a_1 + c \cdot (i - 1)$，其中 $c$ 是某个固定的常数。

例如，以下五个序列是等差数列：$[5, 7, 9, 11]$、$[101]$、$[101, 100, 99]$、$[13, 97]$ 和 $[5, 5, 5, 5, 5]$。而以下四个序列不是等差数列：$[3, 1, 2]$、$[1, 2, 4, 8]$、$[1, -1, 1, -1]$ 和 $[1, 2, 3, 3, 3]$。

给你一个整数序列 $b_1, b_2, \dots, b_n$。请找出任意一个下标 $j$（满足 $1 \le j \le n$），使得若将 $b_j$ 从序列中删除，剩余的 $n-1$ 个元素可以被重新排列，从而构成一个等差数列。如果不存在这样的下标，则输出 $-1$。

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$.

输入的第一行包含一个整数 $n$（$2 \le n \le 2\cdot10^5$）——序列 $b$ 的长度。
第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$-10^9 \le b_i \le 10^9$）——序列 $b$ 的元素。

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.

输出满足条件的下标 $j$（$1 \le j \le n$），使得：若从该序列中删除第 $j$ 个元素，则剩余元素可以重新排列，构成一个等差数列。若存在多个解，可输出其中任意一个；若不存在这样的下标，则输出 $-1$。

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.

第一个样例的说明：如果删除第 $4$ 个元素，可得到等差数列 $[2, 4, 6, 8]$。

第二个样例的说明：原序列本身已是等差数列，因此删除第 $1$ 个或最后一个元素后，仍可得到等差数列。