Carving the cake 2 (Cake 2)

JOI-kun and IOI-chan are twin brothers and sisters. JOI has been enthusiastic about making sweets lately, and JOI tried to bake a cake and eat it today, but when it was baked, IOI who smelled it came, so we decided to divide the cake. became.

The cake is round. We made radial cuts from a point, cut the cake into N pieces, and numbered the pieces counterclockwise from 1 to N. That is, for 1 ≤ i ≤ N, the i-th piece is adjacent to the i − 1st and i + 1st pieces (though the 0th is considered to be the Nth and the N + 1st is considered to be the 1st). The size of the i-th piece was Ai, but I was so bad at cutting that all Ai had different values.

<image>
Figure 1: Cake example (N = 5, A1 = 2, A2 = 8, A3 = 1, A4 = 10, A5 = 9)


I decided to divide these N pieces by JOI-kun and IOI-chan. I decided to divide it as follows:

1. First, JOI chooses and takes one of N.
2. After that, starting with IOI-chan, IOI-chan and JOI-kun alternately take the remaining pieces one by one. However, if you can only take a piece that has already been taken at least one of the pieces on both sides, and there are multiple pieces that can be taken, IOI will choose the largest one and JOI will take it. You can choose what you like.



JOI wants to maximize the total size of the pieces he will finally take.

Task

Given the number N of cake pieces and the size information of N pieces, create a program to find the maximum value of the total size of pieces that JOI can take.

input

Read the following input from standard input.

* The integer N is written on the first line, which means that the cake is cut into N pieces.
* The integer Ai is written on the i-th line (1 ≤ i ≤ N) of the following N lines, which indicates that the size of the i-th piece is Ai.



output

Output an integer representing the maximum value of the total size of pieces that JOI can take to the standard output on one line.

Limits

All input data satisfy the following conditions.

* 1 ≤ N ≤ 20000.
* 1 ≤ Ai ≤ 1 000 000 000.
* Ai are all different.



Input / output example

Input example 1


Five
2
8
1
Ten
9


Output example 1


18


JOI is best to take the pieces as follows.

1. JOI takes the second piece. The size of this piece is 8.
2. IOI takes the first piece. The size of this piece is 2.
3. JOI takes the 5th piece. The size of this piece is 9.
4. IOI takes the 4th piece. The size of this piece is 10.
5. JOI takes the third piece. The size of this piece is 1.



Finally, the total size of the pieces taken by JOI is 8 + 9 + 1 = 18.

Input example 2


8
1
Ten
Four
Five
6
2
9
3


Output example 2


26


Input example 3


15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789


Output example 3


3600242976


The question text and the data used for the automatic referee are the question text and the test data for scoring, which are created and published by the Japan Committee for Information Olympics.





Example

Input

5
2
8
1
10
9


Output

18
#include <bits/stdc++.h>
using namespace std;

#define fo(i, n) for(int i = 0; i < int(n); i ++)
#define ff(i, n) for(int i = 1; i < int(n); i ++)
 
typedef long long ll;

#define INF 1000000000000
 
ll dp[2010][2010];
ll a[2010];
 
 
int main(){
    int N;ll hog,res;
    bool fla;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> a[i];
    if(N == 1) {
        cout << a[0] << endl;
        return 0;
    }
    dp[0][N-1] = a[N-1];

    for(int i = 1; i < N; i++) dp[i][N-1] = a[i-1];
    fla=false;
    for(int i = N-2; i>=1; i--){
        if(fla){
            dp[0][i]=max(dp[0][i+1]+a[i],dp[N-1][i+1]+a[N-1]);
            for(int j=1;j<N;j++){
                dp[j][i]=max(dp[j][i+1]+a[(j+i)%N],dp[j-1][i+1]+a[j-1]);
            }
        }
        else{
            hog=-INF;
            if(a[0]<a[i]){
                hog=dp[0][i+1];
            }
            if(a[N-1]>a[i-1]){
                hog=max(hog,dp[N-1][i+1]);
            }
            dp[0][i]=hog;
            for(int j=1;j<N;j++){
                hog=-INF;
                if(a[j]<a[(i+j)%N]){
                    hog=dp[j][i+1];
                }
                if(a[j-1]>a[(i+j-1)%N]){
                    hog=max(hog,dp[j-1][i+1]);
                }
                dp[j][i]=hog;
            }
        }
        fla=!fla;
    }
    res=-INF;
 
    if(fla){
        for(int i=0;i<N;i++){
            res=max(res,dp[i][1]+a[i]);
        }
    }
    else{
        for(int i=0;i<N;i++){
            res=max(res,dp[i][1]);
        }
    }
    cout<<res<<endl;
    return 0;
}