Излом инерции графика кормления

Для составления графика кормления животных зоопарк объединил дни наблюдений в группы с похожими расходами корма. Для каждого числа групп от 1 до n уже вычислена инерция: сумма квадратов расстояний от наблюдений до центра своей группы.

Числа групп идут по порядку от 1 до n. Чтобы выбрать число групп по излому, для каждого k от 2 до n−1 вычисляется величина излома

E(k) = I(k−1) − 2 · I(k) + I(k+1),

где I(k) — инерция при k группах. Требуется вывести такое k, для которого E(k) максимально.

Если максимальная величина излома достигается при нескольких k, следует вывести наименьшее из них. Округление не применяется: требуется вывести целое число k.

Формат ввода

В первой строке дано целое число n — количество рассчитанных вариантов числа групп.

Во второй строке даны n целых чисел I(1), I(2), ..., I(n) — инерции для 1, 2, ..., n групп соответственно.

Формат вывода

Выведите одно целое число k — число групп, выбранное по максимальной величине излома.

Ограничения

3 ≤ n ≤ 2000.

0 ≤ I(k) ≤ 10^9 для каждого k.

Гарантируется, что I(k+1) ≤ I(k) для всех 1 ≤ k < n.

Пропусков в данных нет. Все значения инерции являются целыми числами. Величины излома определены хотя бы для одного значения k, так как n ≥ 3.