У Гудвина есть последовательность чисел из которой он хочет удалить три элемента так, чтобы последовательность была наиболее симпатичной.

Кривизна последовательности задается функцией  , то есть разностью, между суммой элементов, стоящих на нечетных местах, и суммой элементов, стоящих на четных местах.

После удаления из последовательности трех элементов все остальные сдвигаются на нужные места. Например, из последовательности {1, 2, 3, 4, 5} можно получить последовательность {2, 4}.

В первой строке записано целое число n (4 ≤ n ≤ 10⁶) — количество элементов в исходной последовательности. Во второй строке записаны n разделенных пробелами целых чисел — члены последовательности, разделенные пробелами. Все числа в последовательности по модулю не превышают 10⁹.

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

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

4
1 2 3 4

1

5
1 2 3 4 5

-4

Тесты разделены на группы, но оцениваются отдельно

• n ≤ 81 — 20 баллов
• n ≤ 300 — 10 баллов
• n ≤ 5000 — 20 баллов
• Без дополнительных ограничений — 50 баллов 

Загруженные файлы:

Примечание учителя: