Пирамида из чисел

Пирамида состоит из n строк. Первая строка расположена внизу и содержит n чисел, вторая строка содержит n - 1 чисел, третья n - 2 и так далее. Последняя (верхняя) строка представлена одним числом.

Известны n чисел первой строки. Вторая строка формируется на основе чисел первой строки, третья строка - на основе второй и так далее.

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

Каждый элемент нечетной строки (кроме первой, числа которого заданы) вычисляется так же за исключением того, что вместо минимума находится максимум.

Найдите сумму всех чисел пирамиды.

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

Первая строка содержит количество чисел n в первой строке пирамиды. Вторая строка содержит эти числа. Все числа целые в диапазоне от 0 до 50 000.

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

Выведите сумму всех чисел пирамиды.

Примеры

Примечание

4 строка: min{9,8} = 8

3 строка: max{5, 1 + 8} = 9, max{5 + 1, 8} = 8

2 строка: min{5, 6 + 7 + 8} = 5, min{5 + 6, 7 + 8} = 11, min{5 + 6 + 7, 8} = 8

1 строка: числа заданы в условии задачи

Ответ: 8 + 9 + 8 + 5 + 1 + 8 + 5 + 6 + 7 + 8 = 65