#include <fstream>
using namespace std;

const int maxN=1e5+1;

int n,q;
int pow2n;

int v[maxN];

int binSearch1(int val){
    int res;
    int step=pow2n;

    for(res=1;step>0;step>>=1)
        if(res+step<=n && v[res+step]<=val)
            res+=step;

    if(v[res]==val)
        return res;
    return -1;
}

int binSearch2(int val){
    int res;
    int step=pow2n;

    for(res=1;step>0;step>>=1)
        if(res+step<=n && v[res+step]<=val)
            res+=step;

    return res;
}

int binSearch3(int val){
    int res;
    int step=pow2n;

    for(res=n;step>0;step>>=1)
        if(res-step>=1 && v[res-step]>=val)
            res-=step;

    return res;
}

int main(){
    ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");

    cin>>n;
    for(pow2n=1;pow2n<n;pow2n<<=1);

    for(int i=1;i<=n;i++)
        cin>>v[i];

    cin>>q;
    while(q--){
        int op,x;
        cin>>op>>x;

        if(op==0)
            cout<<binSearch1(x)<<'\n';
        else if(op==1)
            cout<<binSearch2(x)<<'\n';
        else cout<<binSearch3(x)<<'\n';
    }

    return 0;
}