#include <fstream>
using namespace std;
int v[100010];
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int cautbin0(int st,int dr,int x){
    int mid;
    while(st<=dr){
        mid=(st+dr)/2;
        if(v[mid]<=x)
            st=mid+1;
        else
            dr=mid-1;
    }
    mid=(st+dr)/2;
    if(v[mid]>x)
        mid--;
    if(v[mid]==x)
        return mid;
    return -1;
}
int cautbin1(int st,int dr,int x){
    int mid;
    while(st<dr){
        mid=(st+dr)/2;
        if(v[mid]<=x)
            st=mid+1;
        else
            dr=mid;
    }
    mid=(st+dr)/2;
    if(v[mid]>x)
       --mid;
    return mid;
}
int cautbin2(int st,int dr,int x){
    int mid;
    while(st<dr){
        mid=(st+dr)/2;
        if(v[mid]<x)
            st=mid+1;
        else
            dr=mid;
    }
    mid=(st+dr)/2;
    if(v[mid]<x)
       ++mid;
    return mid;
}
int main(){
    int i,n,m,tip,val;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    while(m--){
          fin>>tip>>val;
          if(tip==0)
             fout<<cautbin0(1,n,val)<<"\n";
          if(tip==1)
             fout<<cautbin1(1,n,val)<<"\n";
          if(tip==2)
             fout<<cautbin2(1,n,val);
    }
    return 0;
}