Uolevi wants to form a secret society in Syrjälä. All of Syrjälä's inhabitants live along a very long road such that each house except the first and the last has two neighbors. Uolevi wants to recruit members to the secret society. For each house he knows that the resident of the house would add value a_i to the society. In order to avoid awkward situations Uolevi doesn't want that any two members of the secret society are neighbors. Compute the maximum value of residents Uolevi can recruit.

Input

The first line of the input contains integer n. The next line contains n integers, a_1, \ldots, a_n.

Output

Output one integer, the maximum value for recruiting people to the secret society.

Constraints

• 1 \le n \le 10^5
• 1 \le a_i \le 10^5

Examples

Input:

6
5 2 6 3 3 7

Output:

18

Input:

4
2 10 7 1

Output:

11