# include <stdio.h>
int a[100005],i,j,k,q,n,m,x,y;
void caut (int x)
{

int i=1,j=n;
k=(i+j)/2;
while (x!=a[k] && i==j)
{
if (x>a[k])
{
i=k;
k=(i+j+1)/2;
}
else
{
j=k;
k=(i+j+1)/2;
}
}
if (y==0)
{
while (a[k]==x)
k++;
printf ("%i\n",k-1);
}
if (y==1)
{
if (a[k]==x)
{
while (a[k]==x)
k--;
printf ("%i\n",k+1);
}
else
{
while (a[k]>x)
k--;
printf ("%i\n",k);
}
}
if (y==2)
{
if (a[k]==x)
{
while (a[k]==x)
k++;
printf ("%i\n",k-1);
}
else
{
while (a[k]<x)
k++;
printf ("%i",k);



}


}

}











int main ()
{
freopen ("cautbin.in","r",stdin);
freopen ("cautbin.out","w",stdout);
scanf ("%i",&n);
for (i=1;i<=n;i++)
scanf ("%i",&a[i]);
scanf ("%i",&m);
for (q=1;q<=m;q++)
{
scanf ("%i%i",&y,&x);
caut (x);
}
return 0;
}