#include <fstream>
#define DIM 100005

using namespace std;

int N,v[DIM],x,y,M;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int cautbin0(int x){
    int p,u,mid;
    p=1;
    u=N;
    while(p<=u){
        mid=(p+u)>>1;
        if(x>=v[mid])
            p=mid+1;
        else
            u=mid-1;
    }
    if(v[p-1]==x)
        return p-1;
    return -1;
}
int cautbin1(int x){
    int p,u,mid;
    p=1;
    u=N;
    while(p<=u){
        mid=(p+u)>>1;
        if(v[mid]<=x)
            p=mid+1;
        else
            u=mid-1;
    }
    return p-1;
}
int cautbin2(int x){
    int p,u,mid;
    p=1;
    u=N;
    while(p<=u){
        mid=(p+u)>>1;
        if(v[mid]>=x)
            u=mid-1;
        else
            p=mid+1;
    }
    return u+1;
}
int main(){
    fin>>N;
    for(int i=1;i<=N;i++)
        fin>>v[i];
    fin>>M;
    while(M--){
        fin>>x>>y;
        if(x==0)
            fout<<cautbin0(y)<<"\n";
        if(x==1)
            fout<<cautbin1(y)<<"\n";
        if(x==2)
            fout<<cautbin2(y)<<"\n";
    }
    fin.close();fout.close();
    return 0;
}