#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
int queries[MAXN][MAXN];
int values[MAXN];
int nbElem;
int calcQueries(int deb, int fin)
// Calcule toutes les requetes [i, (deb+fin)/2] et [(deb+fin)/2+1, i]
{
if (deb >= fin)
return 0;
int mid = (deb + fin) / 2;
int ret = calcQueries(deb,mid) + calcQueries(mid+1, fin) + fin - deb-1;
int mid2 = (deb + mid) / 2;
for (int i(deb); i < mid; ++i)
if (i <= mid2)
{
queries[i][mid] = Secret(queries[i][mid2], queries[mid2+1][mid]);
ret++;
}
int mid3 = (mid + 1 + fin) / 2;
for (int i(mid+2); i <= fin; ++i)
if (i > mid3)
{
queries[mid+1][i] = Secret(queries[mid+1][mid3], queries[mid3+1][i]);
ret++;
}
return ret;
}
int solve(int deb, int fin, int reqDeb, int reqFin)
{
if (deb == fin)
return values[deb];
int mid = (deb + fin) / 2;
if (reqFin <= mid)
return solve(deb, mid, reqDeb, reqFin);
if (reqDeb > mid)
return solve(mid+1, fin, reqDeb, reqFin);
// reqDeb <= mid < reqFin
return Secret(queries[reqDeb][mid], queries[mid+1][reqFin]);
}
void Init(int N, int A[]) {
nbElem = N;
for (int i(0); i < N; ++i)
values[i] = queries[i][i] = A[i];
cerr << "nombre de requetes : " << calcQueries(0, N-1) << endl;
}
int Query(int L, int R) {
return solve(0, nbElem-1, L, R);
}
