#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int pref[8][1001];
int suff[8][1001];
int a[1001];
int f(int a, int b) {
if (a == -1) {
return b;
}
if (b == -1) {
return a;
}
return Secret(a, b);
}
void build(int d, int tl, int tr) {
if (tl > tr) {
return;
}
int tm = (tl + tr) >> 1;
pref[d][tm] = a[tm];
for (int j = tm + 1; j <= tr; j++) {
pref[d][j] = f(pref[d][j - 1], a[j]);
}
// cout << "ASDOUJNASLD ";
// for (int j = tm; j <= tr; j++) {
// cout << pref[0][j] << ' ';
// }
// cout << endl;
suff[d][tm] = -1;
for (int j = tm - 1; j >= tl; j--) {
suff[d][j] = f(a[j], suff[d][j + 1]);
}
build(d + 1, tl, tm - 1);
build(d + 1, tm + 1, tr);
}
int nn = 0;
void Init(int N, int A[]) {
for (int i = 0; i < N; i++) {
a[i] = A[i];
}
nn = N;
build(0, 0, N - 1);
}
int get(int d, int tl, int tr, int l, int r) {
int tm = (tl + tr) >> 1;
if (l <= tm && tm <= r) {
// cout << d << ' ' << tm << endl;
// cout << "? " << suff[d][l] << ' ' << pref[d][r] << endl;
return f(pref[d][r], suff[d][l]);
} else if (r < tm) {
return get(d + 1, tl, tm - 1, l, r);
} else {
return get(d + 1, tm + 1, tr, l, r);
}
}
int Query(int l, int r) {
return get(0, 0, nn - 1, l, r);
}
