Wave Coffee Company has decided to expand to Oopse and open new coffee shops so that every citizen can enjoy their world-famous coffee.

Oopse consists of a single road with n buildings on one side. Wave Coffee Company wishes that each building along the road has a coffee shop either in the same building or in an adjacent building.

Your task is to find the cheapest way which comforts Wave Coffee Company's wish.

Input

The first line contains a single integer: n, the number of buildings on the road. The second line contains n integers, x_1,x_2,...,x_n, where x_i is the cost of renting premises for a coffee shop in building i.

Output

Output a single integer, the minimum rent which comforts Wave Coffee Company's wish.

Limits

• 1 \le n \le 10^6
• 1 \le x_1,x_2,...x_n \le 10^3

Example

Input:

6
2 7 1 7 7 4

Output:

7

Explanation:

Wave Coffee can open coffee shops in buildings 1, 3, and 6, for a total rent of 2+1+4=7.