#include <fstream>

using namespace std;

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

int n, m;
int v[100005];

int t0(int x) {
    int st=1,dr=n,t0=-1;
    while (st<=dr) {
        int mij=st+(dr - st)/ 2;
        if (v[mij]==x) {
            t0=mij;
            st=mij+1;
        } else if (v[mij] < x) {
            st=mij+1;
        } else {
            dr=mij-1;
        }
    }
    return t0;
}

int t1(int x) {
    int st=1,dr=n, t1=-1;
    while (st<=dr) {
        int mij=st+(dr - st)/2;
        if (v[mij]<=x) {
            t1=mij;
            st=mij+1;
        } else {
            dr=mij-1;
        }
    }
    return t1;
}

int t2(int x) {
    int st=1, dr=n, t2=-1;
    while (st<=dr) {
        int mij=st+(dr-st)/2;
        if (v[mij]>=x) {
            t2=mij;
            dr=mij - 1;
        } else {
            st=mij + 1;
        }
    }
    return t2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    cin>>m;
    for (int i=0; i<m; i++) {
        intt,x;
        cin>>t>>x;
        if (t == 0)
        cout<<t0(x)<<"\n";
        else if(t == 1)
        cout<<t1(x)<<"\n";
        else
         cout<<t2(x)<<"\n";
    }

    return 0;
}