Pyramid of Numbers

The pyramid is structured with n rows. Starting from the bottom, the first row contains n numbers, the second row has n - 1 numbers, the third row has n - 2, continuing in this manner until the top row, which consists of a single number.

The numbers in the first row are provided. Each subsequent row is derived from the row directly below it.

For even-numbered rows, each element is calculated as the last digit of the minimum of two sums: the sum of all elements to the left of the current element in the previous row, and the sum of all elements to the right of the current element in the previous row.

For odd-numbered rows (except the first row, which is given), each element is determined similarly, but using the maximum of the two sums instead of the minimum.

Your task is to compute the sum of all numbers in the pyramid.

Input

The first line contains the integer n, representing the number of numbers in the first row of the pyramid. The second line lists these numbers, which are integers ranging from 0 to 50,000.

Output

Print the sum of all the numbers in the pyramid.

Examples

Note

For the 4th row: min{9, 8} = 8

For the 3rd row: max{5, 1 + 8} = 9, max{5 + 1, 8} = 8

For the 2nd row: min{5, 6 + 7 + 8} = 5, min{5 + 6, 7 + 8} = 11, min{5 + 6 + 7, 8} = 8

For the 1st row: the numbers are given as part of the problem statement

The total sum is: 8 + 9 + 8 + 5 + 1 + 8 + 5 + 6 + 7 + 8 = 65