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

Піраміда складається з 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