#include<fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int n,a[100010],m,x,y;
int caut1(int x){
     int st=1,dr=n,piv;
     while(st<=dr){
        piv=st+(dr-st)/2;
        if(a[piv]<=x)st=piv+1;
         else dr=piv-1;
     }
     piv=st+(dr-st)/2;
     while(a[piv]>x)piv--;
     while(piv>n)piv--;
     if(a[piv]==x)return piv;
     return -1;
}
int caut2(int x){
     int st=1,dr=n,piv;
     while(st<=dr){
                  piv=(dr+st)/2;
                  if(a[piv]<=x)dr=piv-1;
                  else st=dr+1;
     }
     piv=st+(dr-st)/2;
     while(a[piv]<=x)piv++;
     if(a[piv-1]<=x)return piv-1;
}
int caut3(int x){
    int st=1,dr=n,piv;
     while(st<=dr){
        piv=st+(dr-st)/2;
        if(a[piv]<=x)st=piv+1;
         else dr=piv-1;
     }
     piv=st+(dr-st)/2;
     while(a[piv]>=x)piv--;
     if(a[piv+1]<=x)return piv+1;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    while(m--){
               cin>>x>>y;
               if(x==0)cout<<caut1(y)<<"\n";
               if(x==1)cout<<caut2(y)<<"\n";
               if(x==2)cout<<caut3(y)<<"\n";
               }
}