#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
const int nmax=1e3+42;
/*
int Secret(int x,int y)
{
//cout<<"Secret "<<x<<" "<<y<<endl;
int ret;
//cin>>ret;
ret=x+y/2*2;
//cout<<"ret= "<<ret<<endl;
return ret;
}
*/
int n,inp[nmax];
map< pair<int,int>,int> seen;
void go(int l,int r)
{
if(l==r)
{
seen[{l,r}]=inp[l];
return;
}
int av=(l+r)/2;
go(l,av);
seen[{av,av}]=inp[av];
for(int i=av-1;i>=l;i--)
seen[{i,av}]=Secret(inp[i],seen[{i+1,av}]);
go(av+1,r);
for(int i=av+2;i<=r;i++)
seen[{av+1,i}]=Secret(seen[{av+1,i-1}],inp[i]);
}
void Init(int N, int A[])
{
n=N;
for(int i=0;i<n;i++)inp[i]=A[i];
go(0,n-1);
}
int solve(int l,int r,int lq,int rq)
{
int av=(l+r)/2;
if(rq<=av)return solve(l,av,lq,rq);
if(av<lq)return solve(av+1,r,lq,rq);
return Secret(seen[{lq,av}],seen[{av+1,rq}]);
}
int Query(int l,int r)
{
if(seen.count({l,r}))return seen[{l,r}];
return solve(0,n-1,l,r);
}
/*
int nnn=8,a[8]={1, 4, 7, 2, 5, 8, 3, 6};
int main()
{
Init(nnn,a);
cout<<Query(0,3)<<endl;//13
cout<<Query(1,7)<<endl;//32
cout<<Query(5,5)<<endl;//8
cout<<Query(2,4)<<endl;//13
return 0;
}
*/
