#include "secret.h"
#include <iostream>
using namespace std;
int n;
int cal[1005][1005];
void build(int l, int r, int A[]) {
int mid = (l + r) / 2;
cal[mid][mid] = A[mid];
cal[mid+1][mid+1] = A[mid+1];
for (int i = mid-1; i >= l; i--) cal[i][mid] = Secret(A[i], cal[i+1][mid]);
for (int i = mid+2; i <= r; i++) cal[mid+1][i] = Secret(cal[mid+1][i-1], A[i]);
if (l < mid) build(l, mid, A);
if (mid+1 < r) build(mid+1, r, A);
}
int query(int wantL, int wantR, int l = 0, int r = n-1) {
int mid = (l + r) / 2;
if (l == r) return cal[l][r];
if (wantL <= mid && wantR > mid)
return Secret( cal[wantL][mid], cal[mid+1][wantR] );
if (wantL > mid) return query(wantL, wantR, mid+1, r);
else return query(wantL, wantR, l, mid);
}
void Init(int N, int A[]) {
n = N;
build(0, n-1, A);
}
int Query(int L, int R) {
return query(L, R);
}
/*
8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4
ans:
13
32
8
13
*/
