#include<fstream>
using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");
int a[100002], n,m,v,b;

int c(int nr)
{
    int s=1,f=n,mij,rez=-1;
while(s<=f)
{
           mij=(s+f)/2;
           if(a[mij]==nr)
           {
                         rez=mij; s=mij+1;
           }
           if(a[mij]>nr) 
           f=mij-1;
           if(a[mij]<nr)
            s=mij+1;
} 
return rez; 
}

int c2 (int nr)
{
    int s=1,f=n,mij,rez;
while(s<=f)
{
           mij=(s+f)/2;
           if(a[mij]<=nr)
                         {
                          rez=mij; s=mij+1;
                          }
                          else f=mij-1;
}
return rez;
}

int c3(int nr)
{
    int s=1,f=n,mij,rez;
while(s<=f)
{
           mij=(s+f)/2;
           if(a[mij]>=nr){
                          rez=mij; f=mij-1;
                          }
           else s=mij+1;
}
return rez;
}

int main()
{
    int i;
    in>>n;
for(i=1;i<=n;i++)
in>>a[i];
in>>m;
for(i=1;i<=m;i++)
{ 
in>>v>>b;
if(v==0)out<<c(b)<<"\n";
if(v==1)out<<c2(b)<<"\n";
if(v==2)out<<c3(b)<<"\n";
}
 return 0;   
 }