#include <fstream>
#define N 100010
int v[N];
int bsearch0 (int p, int u, int key) {
int m;
while (p <= u) {
m = (p + u) / 2;
if (v[m] <= key)
p = m + 1;
else
u = m - 1;
}
m = (p + u) / 2;
if (v[m] > key) m --;
if (v[m] == key)
return m;
return -1;
}
int bsearch1 (int p, int u, int key) {
int m, n = u;
while (p < u){
m = (p + u) / 2;
if (v[m] <= key;
p = m + 1;
else
u = m;
}
m = (p + u) / 2;
if (v[m] > key)
-- m;
return m;
}
int bsearch2 (int p, int u, int key) {
int m;
while (p < u) {
m = (p + u) / 2;
if (v[m] < key)
p = m + 1;
else
u = m;
}
m = (p + u) / 2;
if (v[m] < key)
++ m;
return m;
}
int main () {
int i, n, m, tip, val;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
fin>>n;
for (i=1;i<=n;++i)
fin >>v[i];
fin>>m;
while(m--)
{
    fin>>tip>>val;
    if(tip==0)
    fout<<bsearch0(1,n,val);
    if(tip==1)
    fout<<bsearch1(1,n,val);
    if(tip==2)
    fout<<bsearch2(1,n,val);
}
return 0;

}
}