#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int m,v[100000],i,n,intr,mij,trb;
inline int cautare_binara0(int x){
    int st,dr,m,j;
    st=1;
    dr=n;
    m=0;
    while(st<=dr){
        m=st+(dr-st)/2;
        if(v[m]<=x)
            st=m+1;
        else
            dr=m-1;
    }
    m = (st + dr) / 2;
    if (v[m] > x) m --;
    if (v[m] == x)
        return m;
    return -1;
}
inline int cautare_binara1(int x){
    int st,dr,m,j;
    st=1;
    dr=n;
    m=0;
    while(st<dr){
        m=st+(dr-st)/2;
        if(v[m]<=x)
            st=m+1;
        else
            dr=m-1;
    }
    m = (st + dr) / 2;
    if (v[m] > x)
       -- m;
    return m;
}
inline int cautare_binara2(int x){
    int st,dr,m,j;
    st=1;
    dr=n;
    m=0;
    while(st<dr){
        m=st+(dr-st)/2;
        if(v[m]<x)
            st=m+1;
        else
            dr=m-1;
    }
   m = (st + dr) / 2;
   if (v[m] < x)
       ++ m;
    return m;
}
int main(){
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(i=1;i<=m;i++){
        int j;
        fin>>trb;
        fin>>intr;
        if(trb==0)
            fout<<cautare_binara0(intr)<<'\n';
        if(trb==1)
            fout<<cautare_binara1(intr)<<'\n';
        if(trb==2)
            fout<<cautare_binara2(intr)<<'\n';
    }
    return 0;
}