#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

int v[100001],n,nr_op,op,val,fals=-1;

int cautareBinara0(int st,int dr,int val){
    int mijloc;
    while(st<=dr){
        mijloc=(st+dr)/2;
        if(v[mijloc]<=val)
            st=mijloc+1;
        else
            dr=mijloc-1;
    }
    mijloc=(st+dr)/2;

    if(v[mijloc]>val)
        mijloc--;
    if(v[mijloc]==val)
        return mijloc;
    return fals;
}

int cautareBinara1(int st,int dr,int val){
    int mijloc;
    while(st<dr){
        mijloc=(st+dr)/2;
        if(v[mijloc]<=val)
            st=mijloc+1;
        else
            dr=mijloc;
    }
    mijloc=(st+dr)/2;

    if(v[mijloc]>val)
        mijloc--;
    return mijloc;
}

int cautareBinara2( int st,int dr,int val){
        int mijloc;
    while(st<dr){
        mijloc=(st+dr)/2;
        if(v[mijloc]<val)
            st=mijloc+1;
        else
            dr=mijloc;
    }
    mijloc=(st+dr)/2;

    if(v[mijloc]<val)
        mijloc++;
    return mijloc;
}

int main() {
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    in>>nr_op;
    while(nr_op){
        in>>op>>val;
        nr_op--;
        if(op==0)
            out<<cautareBinara0(1,n,val)<<'\n';
        if(op==1)
            out<<cautareBinara1(1,n,val)<<'\n';
        if(op==2)
            out<<cautareBinara2(1,n,val)<<'\n';
    }
    return 0;
}