#include <stdio.h>
#include <stdlib.h>
int a[100000];

int cautabin0(int x,int left,int right)
{
int mijloc;
while(left<=right)
{
mijloc=(left+right)/2;
if(a[mijloc]<=x)
left=mijloc+1;
else
right=mijloc-1;
}
mijloc=(left+right)/2;
if(a[mijloc]>x) mijloc--;
if(a[mijloc]==x) return mijloc;
else return -1;
}
int cautabin1(int x,int left,int right)
{
int mijloc;
while(left<right)
{
mijloc=(left+right)/2;
if(a[mijloc]<=x)
left=mijloc+1;
else
right=mijloc;
}
mijloc=(left+right)/2;
if(a[mijloc]>x)
mijloc--;
return mijloc;
}
int cautabin2(int x,int left,int right)
{
int mijloc;
while(left<right)
{
mijloc=(left+right)/2;
if(a[mijloc]<x)
left=mijloc+1;
else
right=mijloc;
}
mijloc=(left+right)/2;
if(a[mijloc]<x)
mijloc++;
return mijloc;
}
 
int main()
{
int n,i,j,m,quest1,quest2;
FILE *f=fopen("cautbin.in","r");
FILE *g=fopen("cautbin.out","w");
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%d",&a[i]);
fscanf(f,"%d",&m);
for(j=0;j<m;j++)
{
fscanf(f,"%d %d",&quest1,&quest2);
if(quest1==0)
fprintf(g,"%d\n",cautabin0(quest2,1,n));
if(quest1==1)
fprintf(g,"%d\n",cautabin1(quest2,1,n));
if(quest1==2)
fprintf(g,"%d\n",cautabin2(quest2,1,n));
}
return 0;
}