#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
int n, a[1005], f[20][1005], pref[25], suf[25];
void calculate(int l, int r, int depth)
{
if(r-l+1 <= 4) return;
int mid = (l+r)/2;
f[depth][mid] = a[mid];
for(int i = mid-1; i >= l; i--) f[depth][i] = Secret(a[i], f[depth][i+1]);
f[depth][mid+1] = a[mid+1];
for(int i = mid+2; i <= r; i++) f[depth][i] = Secret(f[depth][i-1], a[i]);
calculate(l, mid, depth+1);
calculate(mid+1, r, depth+1);
}
void Init(int N, int A[]) {
n = N;
for(int i = 0; i < n; i++) a[i] = A[i];
if(n > 4) calculate(0, n-1, 0);
else{
pref[0] = a[0];
for(int i = 1; i < n; i++) pref[i] = Secret(pref[i-1], a[i]);
suf[n-1] = a[n-1];
for(int i = n-2; i >= 0; i--) suf[i] = Secret(a[i], suf[i+1]);
}
}
int solve(int l, int r, int depth, int tl, int tr)
{
if(r-l+1 <= 4){
cout<<"Wtf";
while(true); //This case should never happen
return -1;
}
int mid = (l+r)/2;
if(tr < mid) return solve(l, mid, depth+1, tl, tr);
else if(tr == mid) return f[depth][tl];
else if(tl <= mid) return Secret(f[depth][tl], f[depth][tr]);
else if(tl == mid+1) return f[depth][tr];
else return solve(mid+1, r, depth+1, tl, tr);
}
int Query(int l, int r) {
if(r-l+1 <= 4){
int ans = a[l];
for(int i = l+1; i <= r; i++) ans = Secret(ans, a[i]);
return ans;
//I will deal with this later
}
return solve(0, n-1, 0, l, r);
}
