#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
const int def = 1001;
int n;
int a[def];
int f[10][def];
// int Secret(int X, int Y) {
// return (X + 2 * (Y / 2) < 1e9) ? (X + 2 * (Y / 2)) : 1e9;
// }
void build(int l, int r, int k){
if (l >= r)
return;
int mid = (l + r) / 2;
int crr = a[mid];
for (int i = mid; i >= l; i--){
f[k][i] = crr;
if (i > l)
crr = Secret(a[i - 1], crr);
}
crr = a[mid + 1];
for (int i = mid + 1; i <= r; i++){
f[k][i] = crr;
if (i < r)
crr = Secret(crr, a[i + 1]);
}
build(l, mid, k + 1);
build(mid + 1, r, k + 1);
}
void Init(int N, int A[]){
n = N;
for (int i = 0; i < n; i++)
a[i] = A[i];
build(0, n - 1, 0);
}
int Query(int l, int r){
int L = 0, R = n - 1, k = 0;
while (1){
int mid = (L + R) / 2;
if (l >= L && r <= R){
if (r == mid)
return f[k][l];
if (l == mid + 1)
return f[k][r];
if (l <= mid && r > mid)
return Secret(f[k][l], f[k][r]);
}
if (r <= mid)
R = mid;
else
L = mid + 1;
k++;
}
}
// main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// if (ifstream("input.txt").good()){
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// }
// int N;
// cin >> N;
// int A[N];
// for (int i = 0; i < N; i++)
// cin >> A[i];
// Init(N, A);
// int q;
// cin >> q;
// while (q--){
// int l, r;
// cin >> l >> r;
// cout << Query(l, r) << endl;
// }
// }
