#include <cstdio>
using namespace std;
FILE* fin=fopen("cautbin.in","r");
FILE* fout=fopen("cautbin.out","w");
int vec[100005];
int cauta0 (int nr) ;
int cauta1 (int nr);
int cauta2 (int nr);
int n;
int main ()
{
int i,m,q,x;
fscanf(fin,"%d", &n);
for (i=1; i<=n; i++)
fscanf(fin,"%d", &vec[i]);
fscanf(fin,"%d", &m);
for(i=1;i<=m;i++)
{
fscanf(fin,"%d %d",&q, &x);
if(!q)
fprintf(fout,"%d\n",cauta0(x));
if (q==1)
fprintf(fout,"%d\n",cauta1(x));
if (q==2)
fprintf(fout,"%d\n",cauta2(x));
}
return 0;
}
int cauta0 (int nr)
{
int m,st,fi;
st=0; fi=n+1;
while (fi-st>1)
{
m=(st+fi)/2;
if (vec[m] <= nr)
st=m+1;
else
fi=m-1;
}
m=(st + fi) / 2;
if (vec[m]>nr) m --;
if (vec[m]==nr)
return m;
return -1;
}
int cauta1 (int nr)
{
int m, st,fi;
st=0; fi=n+1;
while (st < fi)
{
m=(st + fi) / 2;
if (vec[m]<=nr)
st=m + 1;
else
fi=m;
}
m=(st+fi)/2;
if (vec[m]>nr)
-- m;
return m;
}
int cauta2 (int nr)
{
int m,st,fi;
st=0; fi=n+1;
while (st<fi)
{
m=(st+fi)/2;
if (vec[m]<nr)
st=m+1;
else
fi=m;
}
m=(st+fi)/2;
if (vec[m]<nr)
++ m;
return m;
}