Цикл лекций в университете Флатландии посвящен изучению последовательностей.
Профессор называет последовательность целых чисел
\(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 \le n \le 300 000\)).
Вторая строка содержит n целых чисел
\(b_1, b_2, …, b_n (–10^9 \le b_i \le 10^9 )\) .
Выходные данные
Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 2 0 0 |
2 |