#include "secret.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
map<pii, int> mp;
const int NMAX = 10001;
int a[NMAX];
int n;
int xx;
void build(int l, int r){
int m = (l + r) / 2;
if(l == r){
mp[{l, r}] = a[l];
return;
}
build(l, m);
build(m + 1, r);
if(l == 0 && r == n - 1) return;
if((l != xx + 1) || (r != n - 1)){
for(int i = l; i <= m; i++){
int x = mp[{i, m}];
int y = mp[{m + 1, r}];
mp[{i, r}] = Secret(x, y);
}
}
if(r - l > 1){
if((l != 0) || (r != xx)){
for(int i = r; i >= m + 1; i--){
int x = mp[{l, m}];
int y = mp[{m + 1, i}];
mp[{l, i}] = Secret(x, y);
}}}
}
void Init(int N, int A[]) {
n = N;
for(int i = 0; i < n; i++) a[i] = A[i];
//cout << 1;
xx = (n - 1) / 2;
build(0, n - 1);
}
int Query(int L, int R) {
//cout << n << "\n";
int l = 0, r = n - 1;
if(L == R){
return a[R];
}
while(true){
int m = (l + r) / 2;
if(R <= m) {
r = m;
continue;
}
if(L > m){
l = m + 1;
continue;
}
break;
}
int m = (l + r) / 2;
int x = mp[{L, m}];
int y = mp[{m + 1, R}];
return Secret(x, y);
}
