#include <vector>
#include "secret.h"
#include <iostream>
using namespace std;
int n;
vector<int> v, li[1005][1005];
void dnc(int lf, int rg){
if(lf == rg) return;
int md = (lf + rg) / 2;
// cout << lf << " " << md << endl;
// cout << md + 1 << " " << rg << endl;
vector<int> w;
for(int i = md; i >= lf; i --){
if(i == md) w.push_back(v[i]);
else w.push_back(Secret(v[i], w.back()));
}
li[lf][md] = w;
w.clear();
for(int i = md + 1; i <= rg; i ++){
if(i == md + 1) w.push_back(v[i]);
else w.push_back(Secret(w.back(), v[i]));
}
li[md + 1][rg] = w;
w.clear();
dnc(lf, md); dnc(md + 1, rg);
}
void Init(int _n, vector<int> _v){
n = _n; v = _v;
dnc(0, n - 1);
}
pair<int, int> solve(int cl, int cr, int lf, int rg){
int md = (cl + cr) / 2;
if(lf <= md && md < rg) return {cl, cr};
if(md < lf) return solve(md + 1, cr, lf, rg);
else return solve(cl, md, lf, rg);
}
int Query(int l, int r){
if(l == r) return v[l];
pair<int, int> get = solve(0, n - 1, l, r);
int cl = get.first, cr = get.second;
int md = (cl + cr) / 2;
int lf = li[cl][md][md - l];
int rg = li[md + 1][cr][r - md - 1];
// cout << lf << " " << rg << endl;
return Secret(lf, rg);
}
