#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define pb push_back
#define sz(x) (int)x.size()
const int id = 1e9+7;
const int MX = (1<<10);
int tab[10][MX];
vector<int> v;
int F(int x, int y){
if(x == id) return y;
if(y == id) return x;
return Secret(x, y);
}
void divi(int L, int R, int lev){
if(L == R) return;
int M = (L+R)/2;
int nex = lev-1;
tab[nex][M] = v[M];
for(int i=M-1; i>=L; i--) tab[nex][i] = F(v[i], tab[nex][i+1]);
tab[nex][M+1] = v[M+1];
for(int i=M+2; i<=R; i++) tab[nex][i] = F(tab[nex][i-1], v[i]);
divi(L, M, nex);
divi(M+1, R, nex);
}
void Init(int N, int A[]){
v.resize(MX, id);
for(int i=0; i<N; i++) v[i] = A[i];
divi(0, MX-1, 10);
}
int Query(int l, int r){
if(l == r) return v[l];
int c = l + MX, d = r + MX;
int lev = 31 - __builtin_clz(c^d);
return F(tab[lev][l], tab[lev][r]);
}
