Задача 8. Гармоническая последовательность

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:sequence.in   Ограничение памяти:256 Мб
Выходной файл:sequence.out  
Максимальный балл:100  

Условие

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

Профессор называет последовательность целых чисел a1, a2, …, aN гармоничной, если каждое число, кроме a1 и aN, равно сумме соседних: a2 = a1 + a3, a3 = a2 + a4, …, aN − 1 = aN − 2 + aN. Например, последовательность [1, 2, 1,  − 1] является гармоничной, поскольку 2 = 1 + 1, и 1 = 2 + ( − 1).

Рассмотрим последовательности равной длины: A = [a1, a2, …, aN] и B = [b1, b2, …, bN]. Расстоянием между этими последовательностями будем называть величину N(A, B) = |a1 − b1| + |a2 − b2| + ⋯  + |aN − bN|. Например, d([1, 2, 1,  − 1], [1, 2, 0, 0]) = |1 − 1| + |2 − 2| + |1 − 0| + | − 1 − 0| = 0 + 0 + 1 + 1 = 2.

В конце лекции профессор написал на доске последовательность из N целых чисел B = [b1, b2, …, bN] и попросил студентов в качестве домашнего задания найти гармоничную последовательность A = [a1, a2, …, aN], такую, что d(A, B) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние d(A, B).

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

Формат входного файла

Первая строка входного файла содержит целое число N — количество элементов в последовательности.

Вторая строка содержит n целых чисел b1, b2, …, bN.

Формат выходного файла

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

Ограничения

3 ≤ N ≤ 300 000;  − 109 ≤ bi ≤ 109

Пояснения к примеру

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

Описание подзадач и системы оценивания

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

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

Подзадача 1 (14 баллов)

N = 3,  − 10 ≤ bi ≤ 10

Подзадача 2 (14 баллов)

3 ≤ N ≤ 500,  − 100 ≤ bi ≤ 100

Подзадача 3 (16 баллов)

3 ≤ N ≤ 100 000,  − 100 ≤ bi ≤ 100

Подзадача 4 (16 баллов)

3 ≤ N ≤ 1000,  − 109 ≤ bi ≤ 109

Подзадача 5 (40 баллов)

3 ≤ N ≤ 300 000,  − 109 ≤ bi ≤ 109

Получение информации о результатах окончательной проверки

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

Примеры тестов

Входной файл (sequence.in) Выходной файл (sequence.out)
1
4
1 2 0 0
2

0.076s 0.008s 13