#include<bits/stdc++.h>
#include "secret.h"
using namespace std;
const int MAXN = 1010;
int N, ans[MAXN][MAXN];
void divide_and_conquer(int l, int r)
{
if(r - l <= 1) return;
int mid = (l + r) >> 1;
for(int i = mid - 1; l <= i; i--) ans[i][mid] = Secret(ans[i][i], ans[i + 1][mid]);
for(int i = mid + 2; i <= r; i++) ans[mid][i] = Secret(ans[mid][i - 1], ans[i][i]);
divide_and_conquer(l, mid);
divide_and_conquer(mid + 1, r);
}
void Init(int n, int a[])
{
N = n;
for(int i = 0; i < n; i++) ans[i][i] = a[i];
divide_and_conquer(0, N - 1);
}
int findAns(int l, int r, int L, int R)
{
int mid = (l + r) >> 1;
if(L <= mid && mid + 1 <= R) return Secret(ans[L][mid], ans[mid + 1][R]);
if(R <= mid) return findAns(l, mid, L, R);
else return findAns(mid + 1, r, L, R);
}
int Query(int l, int r)
{
if(r - l <= 1) return Secret(ans[l][l], ans[r][r]);
return findAns(0, N - 1, l, r);
}
