D. Лишний элемент
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность $$$a_1, a_2, \dots, a_k$$$ называется арифметической прогрессией, если для всех $$$i$$$ от $$$1$$$ до $$$k$$$ верно равенство $$$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.

Входные данные

В первой строке входных данных записано целое число $$$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$$$.

Выходные данные

Выведите такой индекс $$$j$$$ ($$$1 \le j \le n$$$), что если из заданной последовательности удалить $$$j$$$-й элемент, то оставшиеся элементы можно расставить в таком порядке, что получится арифметическая прогрессия. Если решений несколько, выведите любое из них. Если искомого индекса не существует, то выведите -1.

Примеры
Входные данные
5
2 6 8 7 4
Выходные данные
4
Входные данные
8
1 2 3 4 5 6 7 8
Выходные данные
1
Входные данные
4
1 2 4 8
Выходные данные
-1
Примечание

Пояснение к первому примеру: если удалить $$$4$$$-й элемент, то из полученной последовательности можно составить арифметическую прогрессию $$$[2, 4, 6, 8]$$$.

Пояснение ко второму примеру: исходная последовательность уже является арифметической прогрессией, поэтому мы можем удалить либо $$$1$$$-й элемент, либо последний, и всё равно получим арифметическую прогрессию.