#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> rezultat[2000][2];
int limita , sir[1001] , __rezultat[1001][1001];
inline void Build (const int nod , const int stanga , const int dreapta)
{
if (stanga == dreapta)
{
rezultat[nod][0].push_back(sir[stanga]);
rezultat[nod][1].push_back(sir[stanga]);
return;
}
const int mijloc = (stanga + dreapta) >> 1;
Build(nod + 1 , stanga , mijloc);
Build(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta);
if (nod != 1)
{
rezultat[nod][0].push_back(sir[dreapta]);
for (int indice = dreapta - 1 ; indice >= stanga ; indice--)
{ rezultat[nod][0].push_back(Secret(sir[indice] , rezultat[nod][0].back())); }
reverse(rezultat[nod][0].begin() , rezultat[nod][0].end());
rezultat[nod][1].push_back(sir[dreapta]);
for (int indice = stanga + 1 ; indice <= dreapta ; indice++)
{ rezultat[nod][1].push_back(Secret(rezultat[nod][1].back() , sir[indice])); }
}
}
void Init (int lungime , int __sir[])
{
limita = lungime;
for (int indice = 0 ; indice < limita ; indice++)
{ sir[indice] = __sir[indice]; }
//Build(1 , 0 , lungime - 1);
for (int stanga = limita - 1 ; stanga >= 0 ; stanga--)
{
__rezultat[stanga][stanga] = sir[stanga];
for (int dreapta = stanga + 1 ; dreapta < limita ; dreapta++)
{ __rezultat[stanga][dreapta] = Secret(sir[dreapta] , __rezultat[stanga][dreapta - 1]); }
}
}
int Query (int stanga , int dreapta)
{
return __rezultat[stanga][dreapta];
int nod = 1 , __stanga = 0 , __dreapta = limita - 1;
while (__stanga != __dreapta)
{
const int mijloc = (__stanga + __dreapta) >> 1;
if (dreapta <= mijloc) { nod++; __dreapta = mijloc; }
else if (stanga > mijloc) { nod += ((mijloc - __stanga + 1) << 1); __stanga = mijloc + 1; }
else { break; }
}
if (__stanga == __dreapta)
{ return rezultat[nod][0][0]; }
const int mijloc = (__stanga + __dreapta) >> 1;
return Secret(rezultat[nod + 1][0][stanga - __stanga] , rezultat[nod + ((mijloc - __stanga + 1) << 1)][1][dreapta - (mijloc + 1)]);
}
