#include <fstream>
#define DIM 100002

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int N,M,v[DIM],op,a,b;
int caut1(int x){
    int p=1,u=N,mid=1,sol=-1;
    while(p<=u){
        mid=(p+u)>>1;
        if(v[mid]==x){
            sol=mid;
            break;
        }
        if(v[mid]<x)
            p=mid+1;
        else
            u=mid-1;
    }
    if(sol==-1)
        return -1;
    while(v[mid]==x)
        mid++;
    return mid-1;
}
int caut2(int x){
    int p=1,u=N,mid;
    while(p<=u){
        mid=(p+u)>>1;
        if(v[mid]<x)
            p=mid+1;
        else{
            if(v[mid]>x)
                u=mid-1;
            else
                break;
        }
    }
    while(v[mid]<=x && mid<=N)
        mid++;
    return mid-1;
}
int caut3(int x){
    int p=1,u=N,mid;
    while(p<=u){
        mid=(p+u)>>1;
        if(v[mid]<x)
            p=mid+1;
        else{
            if(v[mid]>x)
                u=mid-1;
            else
                break;
        }
    }
    while(v[mid]>=x && mid>=1)
        mid--;
    return mid+1;
}
int main(){
    fin>>N;
    for(int i=1;i<=N;i++)
        fin>>v[i];
    fin>>M;
    for(int i=1;i<=M;i++){
        fin>>op>>a;
        if(op==0)
            fout<<caut1(a)<<"\n";
        if(op==1)
            fout<<caut2(a)<<"\n";
        if(op==2)
            fout<<caut3(a)<<"\n";
    }
    fin.close();fout.close();
    return 0;
}