Рабочее место участника

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел `a_1,\ a_2,\ …,\ a_n` гармоничной, если каждое число, кроме `a_1` и `a_n`, равно сумме соседних: `a_2\ =\ a_1\ +\ a_3`, `a_3\ =\ a_2\ +\ a_4`, …, `a_{n-1}\ =\ a_{n-2}\ +\ a_n`. Например, последовательность `[1,\ 2,\ 1,\ -1]` является гармоничной, поскольку `2\ =\ 1\ +\ 1`, и `1 = 2\ +\ (-1)`.

Рассмотрим последовательности равной длины: `A\ =\ [a_1,\ a_2,\ …,\ a_n]` и `B\ =\ [b_1,\ b_2,\ …,\ b_n]`. Расстоянием между этими последовательностями будем называть величину `d(A, B) = |a_1\ -\ b_1|\ +\ |a_2\ -\ b_2|\ +\ …\ +\ |a_n\ -\ b_n|`. Например, `d([1,\ 2\ ,1,\ -1],\ [1,\ 2,\ 0,\ 0])\ =\ |1\ -\ 1|\ +\ |2\ -\ 2|\ +\ |1\ -\ 0|\ +\ |-1\ -\ 0|\ =\ 0\ +\ 0\ +\ 1\ +\ 1\ =\ 2`.

В конце лекции профессор написал на доске последовательность из `n` целых чисел `B =\ [b_1,\ b_2,\ …,\ b_n]` и попросил студентов в качестве домашнего задания найти гармоничную последовательность `A\ =\ [a_1,\ a_2,\ ..,\ a_n]`, такую, что `d(A, B)` минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние `d(A,\ B)`.

Требуется написать программу, которая по заданной последовательности `B` определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность `A`.

Первая строка входного файла содержит целое число `n` - количество элементов в последовательности (`3 ≤ n ≤ 300 000`).

Вторая строка содержит `n` целых чисел `b_1,\ b_2,\ …,\ b_n` (`-10^9 ≤ b_i ≤ 10^9`).

Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.

4
1 2 0 0

2

Пояснение к примеру В приведенном примере оптимальной является, например, гармоничная последовательность [1, 2, 1, –1].

В этой задаче пять подзадач. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Внимание! Тест из примера не подходит под ограничения для подзадачи 1, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только подзадачи 1.

`n\ =\ 3`, `-10 ≤ b_i ≤ 10`

`3 ≤ n ≤ 500`, `-100 ≤ b_i ≤ 100`

`3 ≤ n ≤ 100 000`, `-100 ≤ b_i ≤ 100`

`3 ≤ n ≤ 1000`, `-10^9 ≤ b_i ≤ 10^9`

`3 ≤ n ≤ 300 000`, `-10^9 ≤ b_i ≤ 10^9`

По запросу сообщается баллы за каждую подзадачу.