#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstdio>
#include <vector>
#include <iostream>
#include <utility>
#include <queue>
#include <map>
#include <complex>
#define fir first
#define sec second
#define sz(s) (s).size()
#define pb push_back
#define get(n) scanf("%d",&n);
#define gets(s) string s;cin >> (s);
#define prfi(n) printf("%d", &n);
#define prfd(n) printf("%lf", &n);
#define All(s) (s).begin(), (s).end()
#define rep(i,j) for(int (i)=0;(i)<(j);(i)++)
#define For(i,j,k) for(int (i)=(j);(i)<(k);(i)++)
#define drep(i,j) for(int (i)=(j);(i)>=0;(i)--)
#define Ford(i,j,k) for(int (i)=(j);i>=(k);i--)
#define fore(c,v) for(auto (c): (v))
#define lp for(int __=0;__<n;i++)
#define mem(a,b) memset(a,b,sizeof(a));
#define dump(x)  std::cout << #x << " = " << (x) << std::endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using ull = unsigned long long int;
using ll = long long;
using ld = long double;
using pii = std::pair<int,int>;
using pll = std::pair<ll, ll>;
using vi = std::vector<int> ;
using vvi = std::vector<vi> ;
using vll = std::vector<ll>;
using vvll = std::vector<vll>;
using vd = std::vector<double> ;
using vvd = std::vector<vd> ;
using qi = std::queue<int> ;
using vpii = std::vector<std::pair<int, int> >;
using vpll = std::vector<pll>;
using namespace std;

const int Mod = (1e9) + 7;
const int INF = 1e9 + 19;
const ll INFL = 1e18 + 19;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
const int dx2[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
const int dy2[] = {1, 0, -1, 1, 0, -1, 1, 0, -1};
const double EPS = 1e-10;
//_____________________________________Templates_________________________________________//

template<class T1, class T2> inline void chmin(T1 &a, T2 b){if(a > b) a = b;}
template<class T1, class T2> inline void chmax(T1 &a, T2 b){if(a < b) a = b;}
template<class T> inline void pri(T a){cout << a << endl;}
template<class Z> using vec = vector<Z>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
//mainly use for dynamic prog
template<class T1, class T2>
void update(T1 &a, T2 b){
  a += b;
  if(a > Mod) a %= Mod;
}

inline void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

inline void OUT(void){
  cout << "\n";
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

bool pairsort(pll pl, pll pr){
  if(pl.first == pr.first)return pl.second > pr.second;
  return pl.first < pr.first;
}

int cntbit(ll a,int n,int j){int res = 0;For(i,j,n){if(a>>i & 1){res++;}}return res;}
vector<int> make_bit(int a){vector<int> res; for(int i=31;i>=0;i--)if(a&(1<<i))res.pb(i);return res;}
bool stdbit(int a, int b){return a&(1 << b); }
int GCD(int a, int b){if(b > a)return GCD(b,a);if(a%b == 0)return b;else return GCD(b, a%b);}
int LCM(int a, int b){return a*b/GCD(a,b);}
int roundup(int a, int b){if(a % b == 0)return a/b;else return (a+b)/b;}
int rounddown(int a, int b){if(a%b == 0)return a/b;else {return (a-b)/b;}}
ll pow(ll a, ll n){ll res = 1;while(n > 0){if(n&1)res *= a; a *= a; n = n >> 1;}return res;}
ll GetDiviserCount(ll N)//約数の個数
{
  ll res = 1;
  For(i,2,sqrt(N)+1)
  {
    ll cnt = 0;
    while(N%i == 0)
    {
      cnt++;
      N /= i;
    }
    res *= (cnt + 1);
    if(N == 1)break;
  }
  if(N != 1)res *= 2;
  return res;
}
vll GetDivisor(ll N)//約数列挙
{
  vll res;
  for(ll i = 1;i*i <= N;i++)
  {
    if(N%i == 0)
    {
      res.pb(i);
      if(i*i != N)res.pb(N/i);
    }
  }
  sort(All(res));
  return res;
}

struct Modint
{
  using ll = long long int;
  ll x;
  Modint(ll x=0) :x((x%Mod+Mod)%Mod) {}
  Modint operator - ()
  {
   return Modint(-x);
  }
  Modint& operator +=(Modint a)
  {
    x += a.x;
    if(x >= Mod)x -= Mod;
    return *this;
  }
  Modint& operator -=(Modint a)
  {
   if(x < a.x)x += Mod;
   x -= a.x;
   return *this;
  }
  Modint& operator *=(Modint a)
  {
    (x *= a.x) %= Mod;
    return *this;
  }
  Modint operator + (Modint a)
  {
    Modint b(*this);
    b += a;
    return b;
  }
  Modint operator - (Modint a)
  {
    Modint b(*this);
    b -= a;
    return b;
  }
  Modint operator * (Modint a)
  {
    Modint b(*this);
    b *= a;
    return b;
  }
  long long int EXTGCD(long long int a, long long int b, long long int &x, long long int &y)
  {
    if(b==0)
    {
      x = 1;
      y = 0;
      return a;
    }
    long long int g = EXTGCD(b,a%b,y,x);
    y -= (a/b)*x;
    return g;
  }
  Modint inverse()
  {
    long long int a,b;
    EXTGCD(x,Mod,a,b);
    a %= Mod;
    return a;
  }
  Modint pow(ll a)
  {
    Modint res = 1;
    Modint b = x;
    while(a > 0)
    {
      if(a & 1)res *= b;
      a = a >> 1;
      b *= b;
    }
    return res;
  }
  friend ostream& operator<<(ostream& os, const Modint& a);
};
ostream& operator<< (ostream& os, const Modint& a)
{
  os << a.x;
  return os;
}
struct combination
{
  vector<Modint> fact,ifact;
  combination(int n) : fact(n+1), ifact(n+1)
  {
    fact[0] = 1;
    for(int i=1;i<=n;i++)fact[i] = fact[i-1] * i;
    ifact[n] = fact[n].inverse();
    for(int i=n;i>=1;i--)ifact[i-1] = ifact[i] * i;
  }
  Modint operator() (int n,int k)
  {
    return fact[n]*ifact[n-k]*ifact[k];
  }
};
using vm = vector<Modint>;
using vvm = vector<vm>;
template<class Z>
struct MyMatrix
{
  using mat = MyMatrix<Z>;
  vector<vector<Z>> m_dat;
  int m_h;
  int m_w;
  MyMatrix(int h, int w) : m_h(h), m_w(w) ,m_dat(h,vector<Z>(w)) {}
  vector<Z> &operator[] (int idx)
  {
    return m_dat[idx];
  }
  mat Multiple(mat &a)
  {
    mat C(m_h, a.m_w);
    for(int i=0;i<m_h;i++)
    {
      for(int j=0;j<a.m_w;j++)
      {
        for(int k=0;k<m_w;k++)
        {
         C[i][j] += m_dat[i][k] * a[k][j];
        }
      }
    }
    return C;
  }
  mat Pow(ll x)
  {
    mat B(m_h,m_w);
    for(int i=0;i<m_h;i++)
    {
      B[i][i] = 1;
    }
    mat A = *this;
    while(x > 0)
    {
      if(x&1)B = B.Multiple(A);
      A = A.Multiple(A);
      x = x >> 1;
    }
    return B;
  }
  //friend ostream& operator<<(ostream &os, const mat &A);
};
/*
template<class Z>
ostream& operator<<(ostream &os, Matrix<Z>& A)
{
  for(int i=0;i<A.m_h;i++)
  {
    for(int j=0;j<A.m_w;j++)
    {
      os << A[i][j] << " ";
    }
    os << endl;
  }
  return os;
}
*/
template<class T>
using mat = MyMatrix<T>;
//_____________________　following sorce code_________________________//
const int max_n = 3 * (1e5) + 1;
const int max_m = 83 * (1e5) + 1;

int n,m,k;
ll N;
int h,w;
string S;
int a,b,c;
vi v;
int ans;
double x,y,z;
vector<int> G[1010101];
vi arr;
vvll dp;
ll rec(int l,int r)
{
  if(dp[l][r] >= 0)return dp[l][r];
  if(l == r)return dp[l][r] = 0;
  int x = r-l;
  ll res = 0;
  if(x%2 == n%2)
  {
    chmax(res,max(rec(l+1,r)+arr[l], rec(l,r-1)+arr[r-1]));
  }
  else 
  {
    if(arr[l] > arr[r-1])
    {
      res = rec(l+1,r);
    }
    else
    {
      res = rec(l,r-1);
    }
  }
  //OUT(l,r);
  dp[l][r] = res;
  //cout << "dp[" << l << "][" << r << "] = " << dp[l][r] << endl;
  return dp[l][r];
}

void solve()
{
  IN(n);
  rep(i,n)
  {
    IN(a);
    arr.push_back(a);
  }
  rep(i,n)
  {
    arr.push_back(arr[i]);
  }
  ll ans = 0;
  dp = vvll(n+n+3,vll(n+n+3,-1));
  rep(i,n)
  {
    ll res = rec(i,i+n);
    //dump(res);
    chmax(ans,res);
  }
  pri(ans);
}

signed main (int argc, char* argv[]) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int cases=1;
  //IN(cases);
  while(cases--)solve();
  //pri(ans);
  //for(auto c : ans){cout << c << endl;}
  //cout << fixed << setprecision(15) << ans << endl;
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstdio>
#include <vector>
#include <iostream>
#include <utility>
#include <queue>
#include <map>
#include <complex>
#define fir first
#define sec second
#define sz(s) (s).size()
#define pb push_back
#define get(n) scanf("%d",&n);
#define gets(s) string s;cin >> (s);
#define prfi(n) printf("%d", &n);
#define prfd(n) printf("%lf", &n);
#define All(s) (s).begin(), (s).end()
#define rep(i,j) for(int (i)=0;(i)<(j);(i)++)
#define For(i,j,k) for(int (i)=(j);(i)<(k);(i)++)
#define drep(i,j) for(int (i)=(j);(i)>=0;(i)--)
#define Ford(i,j,k) for(int (i)=(j);i>=(k);i--)
#define fore(c,v) for(auto (c): (v))
#define lp for(int __=0;__<n;i++)
#define mem(a,b) memset(a,b,sizeof(a));
#define dump(x)  std::cout << #x << " = " << (x) << std::endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using ull = unsigned long long int;
using ll = long long;
using ld = long double;
using pii = std::pair<int,int>;
using pll = std::pair<ll, ll>;
using vi = std::vector<int> ;
using vvi = std::vector<vi> ;
using vll = std::vector<ll>;
using vvll = std::vector<vll>;
using vd = std::vector<double> ;
using vvd = std::vector<vd> ;
using qi = std::queue<int> ;
using vpii = std::vector<std::pair<int, int> >;
using vpll = std::vector<pll>;
using namespace std;

const int Mod = (1e9) + 7;
const int INF = 1e9 + 19;
const ll INFL = 1e18 + 19;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
const int dx2[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
const int dy2[] = {1, 0, -1, 1, 0, -1, 1, 0, -1};
const double EPS = 1e-10;
//_____________________________________Templates_________________________________________//

template<class T1, class T2> inline void chmin(T1 &a, T2 b){if(a > b) a = b;}
template<class T1, class T2> inline void chmax(T1 &a, T2 b){if(a < b) a = b;}
template<class T> inline void pri(T a){cout << a << endl;}
template<class Z> using vec = vector<Z>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
//mainly use for dynamic prog
template<class T1, class T2>
void update(T1 &a, T2 b){
  a += b;
  if(a > Mod) a %= Mod;
}

inline void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

inline void OUT(void){
  cout << "\n";
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

bool pairsort(pll pl, pll pr){
  if(pl.first == pr.first)return pl.second > pr.second;
  return pl.first < pr.first;
}

int cntbit(ll a,int n,int j){int res = 0;For(i,j,n){if(a>>i & 1){res++;}}return res;}
vector<int> make_bit(int a){vector<int> res; for(int i=31;i>=0;i--)if(a&(1<<i))res.pb(i);return res;}
bool stdbit(int a, int b){return a&(1 << b); }
int GCD(int a, int b){if(b > a)return GCD(b,a);if(a%b == 0)return b;else return GCD(b, a%b);}
int LCM(int a, int b){return a*b/GCD(a,b);}
int roundup(int a, int b){if(a % b == 0)return a/b;else return (a+b)/b;}
int rounddown(int a, int b){if(a%b == 0)return a/b;else {return (a-b)/b;}}
ll pow(ll a, ll n){ll res = 1;while(n > 0){if(n&1)res *= a; a *= a; n = n >> 1;}return res;}
ll GetDiviserCount(ll N)//約数の個数
{
  ll res = 1;
  For(i,2,sqrt(N)+1)
  {
    ll cnt = 0;
    while(N%i == 0)
    {
      cnt++;
      N /= i;
    }
    res *= (cnt + 1);
    if(N == 1)break;
  }
  if(N != 1)res *= 2;
  return res;
}
vll GetDivisor(ll N)//約数列挙
{
  vll res;
  for(ll i = 1;i*i <= N;i++)
  {
    if(N%i == 0)
    {
      res.pb(i);
      if(i*i != N)res.pb(N/i);
    }
  }
  sort(All(res));
  return res;
}

struct Modint
{
  using ll = long long int;
  ll x;
  Modint(ll x=0) :x((x%Mod+Mod)%Mod) {}
  Modint operator - ()
  {
   return Modint(-x);
  }
  Modint& operator +=(Modint a)
  {
    x += a.x;
    if(x >= Mod)x -= Mod;
    return *this;
  }
  Modint& operator -=(Modint a)
  {
   if(x < a.x)x += Mod;
   x -= a.x;
   return *this;
  }
  Modint& operator *=(Modint a)
  {
    (x *= a.x) %= Mod;
    return *this;
  }
  Modint operator + (Modint a)
  {
    Modint b(*this);
    b += a;
    return b;
  }
  Modint operator - (Modint a)
  {
    Modint b(*this);
    b -= a;
    return b;
  }
  Modint operator * (Modint a)
  {
    Modint b(*this);
    b *= a;
    return b;
  }
  long long int EXTGCD(long long int a, long long int b, long long int &x, long long int &y)
  {
    if(b==0)
    {
      x = 1;
      y = 0;
      return a;
    }
    long long int g = EXTGCD(b,a%b,y,x);
    y -= (a/b)*x;
    return g;
  }
  Modint inverse()
  {
    long long int a,b;
    EXTGCD(x,Mod,a,b);
    a %= Mod;
    return a;
  }
  Modint pow(ll a)
  {
    Modint res = 1;
    Modint b = x;
    while(a > 0)
    {
      if(a & 1)res *= b;
      a = a >> 1;
      b *= b;
    }
    return res;
  }
  friend ostream& operator<<(ostream& os, const Modint& a);
};
ostream& operator<< (ostream& os, const Modint& a)
{
  os << a.x;
  return os;
}
struct combination
{
  vector<Modint> fact,ifact;
  combination(int n) : fact(n+1), ifact(n+1)
  {
    fact[0] = 1;
    for(int i=1;i<=n;i++)fact[i] = fact[i-1] * i;
    ifact[n] = fact[n].inverse();
    for(int i=n;i>=1;i--)ifact[i-1] = ifact[i] * i;
  }
  Modint operator() (int n,int k)
  {
    return fact[n]*ifact[n-k]*ifact[k];
  }
};
using vm = vector<Modint>;
using vvm = vector<vm>;
template<class Z>
struct MyMatrix
{
  using mat = MyMatrix<Z>;
  vector<vector<Z>> m_dat;
  int m_h;
  int m_w;
  MyMatrix(int h, int w) : m_h(h), m_w(w) ,m_dat(h,vector<Z>(w)) {}
  vector<Z> &operator[] (int idx)
  {
    return m_dat[idx];
  }
  mat Multiple(mat &a)
  {
    mat C(m_h, a.m_w);
    for(int i=0;i<m_h;i++)
    {
      for(int j=0;j<a.m_w;j++)
      {
        for(int k=0;k<m_w;k++)
        {
         C[i][j] += m_dat[i][k] * a[k][j];
        }
      }
    }
    return C;
  }
  mat Pow(ll x)
  {
    mat B(m_h,m_w);
    for(int i=0;i<m_h;i++)
    {
      B[i][i] = 1;
    }
    mat A = *this;
    while(x > 0)
    {
      if(x&1)B = B.Multiple(A);
      A = A.Multiple(A);
      x = x >> 1;
    }
    return B;
  }
  //friend ostream& operator<<(ostream &os, const mat &A);
};
/*
template<class Z>
ostream& operator<<(ostream &os, Matrix<Z>& A)
{
  for(int i=0;i<A.m_h;i++)
  {
    for(int j=0;j<A.m_w;j++)
    {
      os << A[i][j] << " ";
    }
    os << endl;
  }
  return os;
}
*/
template<class T>
using mat = MyMatrix<T>;
//_____________________　following sorce code_________________________//
const int max_n = 3 * (1e5) + 1;
const int max_m = 83 * (1e5) + 1;

int n,m,k;
ll N;
int h,w;
string S;
int a,b,c;
vi v;
int ans;
double x,y,z;
vector<int> G[1010101];
vi arr;
vvll dp;
ll rec(int l,int r)
{
  if(dp[l][r] >= 0)return dp[l][r];
  if(l == r)return dp[l][r] = 0;
  int x = r-l;
  ll res = 0;
  if(x%2 == n%2)
  {
    chmax(res,max(rec(l+1,r)+arr[l], rec(l,r-1)+arr[r-1]));
  }
  else 
  {
    if(arr[l] > arr[r-1])
    {
      res = rec(l+1,r);
    }
    else
    {
      res = rec(l,r-1);
    }
  }
  //OUT(l,r);
  dp[l][r] = res;
  //cout << "dp[" << l << "][" << r << "] = " << dp[l][r] << endl;
  return dp[l][r];
}

void solve()
{
  IN(n);
  rep(i,n)
  {
    IN(a);
    arr.push_back(a);
  }
  rep(i,n)
  {
    arr.push_back(arr[i]);
  }
  ll ans = 0;
  dp = vvll(n+n+3,vll(n+n+3,-1));
  rep(i,n)
  {
    ll res = rec(i,i+n);
    //dump(res);
    chmax(ans,res);
  }
  pri(ans);
}

signed main (int argc, char* argv[]) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int cases=1;
  //IN(cases);
  while(cases--)solve();
  //pri(ans);
  //for(auto c : ans){cout << c << endl;}
  //cout << fixed << setprecision(15) << ans << endl;
  return 0;
}

```