#include<bits/stdc++.h>
#include "secret.h"
using namespace std;
typedef long long LL;
const int N=(int)1000;
#define pref asdas
#define suf asdss
int pref[N+2][N+2],suf[N+2][N+2];
int arr[N+2],d[N+2][N+2],ans[N+2][N+2];
bool used[N+2][N+2]={};
int n;
namespace Lyphmm{
int Secret(int X, int Y){
return min((LL)X+(LL)2*(Y/2),(LL)1000000000);
}
};
void build_rig(int l,int r,int dep){
pref[dep][l]=arr[l];
for(int i=l+1;i<=r;++i) {
pref[dep][i]=Secret(pref[dep][i-1],arr[i]);
}
return;
}
void dnc(int l,int r,int dep){
if (used[l][r]) return;
if (l>r) return;
if (r-l<=1){
int m=(l+r)/2;
used[l][r]=true;
ans[l][r]=(l==r?arr[l]:Secret(arr[l],arr[r]));
dnc(l,m,dep+1),dnc(m+1,r,dep+1);
return;
}
int m=(l+r)/2;
dnc(l,m,dep+1);
for(int i=l;i<=m;++i){
for(int j=m+1;j<=r;++j) d[i][j]=dep;
}
for(int i=m;i>=l;--i){
if (used[i][m]) continue;
for(int j=m-1;j>=i;--j){
if (used[i][j] && used[j+1][m]){
ans[i][m]=Secret(ans[i][j],ans[j+1][m]);
used[i][m]=true;
break;
}
}
assert(used[i][m]);
}
for(int i=m;i>=l;--i) suf[dep][i]=ans[i][m];
build_rig(m+1,r,dep);
dnc(m+1,r,dep+1);
return;
}
void Init(int num,int a[]){
n=num;
for(int i=1;i<=n;++i) arr[i]=a[i-1];
dnc(1,n,1);
return;
}
int Query(int l, int r){
++l,++r;
if (used[l][r]) return ans[l][r];
int m=(l+r)/2;
int ans=Secret(suf[d[l][r]][l],pref[d[l][r]][r]);
return ans;
}
