#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100001],N;

int bs1(int x){
    int hi, lo, mid=0,last;
    for(lo=1,hi=N;lo<=hi;){
                          mid=lo+(hi-lo)/2;
                          if (v[mid]<x) lo=mid+1;
                          else if (v[mid]>x) hi=mid-1;
                          else return mid;
                          }
    return -1;
}
    
int bs2(int x){
    int hi,lo,mid, last=0;
    for(lo=1,hi=N;lo<=hi;){
                          mid=lo+(hi-lo)/2;
                          if(v[mid]<=x) last=mid,lo=mid+1;
                          else hi=mid-1;
                          }
    return last;
}

int bs3(int x){
    int hi,lo,mid, last=0;
    for(lo=1,hi=N;lo<=hi;){
                          mid=lo+(hi-lo)/2;
                          if(v[mid]>=x) last=mid,hi=mid-1;
                          else lo=mid+1;
                          }
    return last;
}

int main(){
    int m,x,q;
    in>>N;
    for(int i=1;i<=N;i++)in>>v[i];
    in>>m;
    for(;m;--m){
            in>>q;
            in>>x;
            if(q==0) out<<bs1(x)<<"\n";
            else if(q==1) out<<bs2(x)<<"\n";
            else if (q==2) out<<bs3(x)<<"\n";            
            }
    return 0;
}