Shubham and Tushar are 2 thieves and they had decided to rob a FALTU society. FALTU society consists of N houses in a row.Each of the ith house has A[i] number of gold coins.

To rob the whole society they both came up with a plan that they will make total N trips to the society one by one (starting from Shubham) and perform below operation in each trip :

> First the thief (which is going to society) had to choose a house which is not selected in any of the previous trips and this house must be adjacent to the house chosen in the other thief’s last operation. Now assign this house to the current thief.If there are multiple such houses any of them can be chosen.

OR 

>  If there is no such house that satisfies the above condition or this is Shuhbam's first trip then the thief can choose any house that is not selected before. Now the chosen house will be assigned to the current thief.

After these N trips , each thief can have the gold coins present in their assigned houses. They both love gold coins , and each of them is smart enough to perform the optimal moves in order to have the maximum number of gold coins at the end of the robbery.

Find the number of gold coins that each thief will have at the end of the robbery.

NOTE: Thief perform 2nd type of operation if he is unable to perform operation of 1st type.

CUSTOM INPUT OUTPUT is allowed in this question.

CONSTRAINTS:

1)   1<= N<= 3*10^5

2)   1<= A[i] <= 100000000

INPUT:

First line contains N denoting number of houses in the FALTU society.

Second Line contains N spaced integer denoting number of gold coins in each house.

OUTPUT:

Print the maximum number of gold coins Shubham and Tushar will have at the end of the robbery.