#include <fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int v[100001],n,i;
int bin1(int st,int dr, int x){
        int poz=-1;
        while(st<=dr){
           int mid=(st+dr)/2;
           if(x==v[mid]){
            poz=mid;
            st=mid+1;
           }
           else
             if(x<v[mid])
                dr=mid-1;
            else
                st=mid+1;
        }
      return poz;
}
int bin2(int st,int dr,int x){
        int poz=0;
        while(st<=dr){
            int mid=(st+dr)/2;
            if(v[mid]<=x){
                poz=mid;
                st=mid+1;
            }
            else
                dr=mid-1;
        }
        return poz;
}
int bin3(int st,int dr,int x){
        int poz=0;
        while(st<=dr){
            int mid=(st+dr)/2;
            if(v[mid]>=x){
                poz=mid;
                dr=mid-1;
            }
            else
                st=mid+1;
        }
        return poz;
}
int main()
{
    int x,m,tip;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
     cin>>m;
     for(i=1;i<=m;i++){
        cin>>tip>>x;
        if(tip==0)
            cout<<bin1(1,n,x)<<"\n";
        else
             if(tip==1)
                 cout<<bin2(1,n,x)<<"\n";
                else
                    cout<<bin3(1,n,x)<<"\n";
     }


    return 0;
}