#include <fstream>

using namespace std;

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

const int NMAX=100005;
long long v[NMAX];
int N;
int cautare0(long long x) {
    int st=1, dr=N, r=-1;
    while(st<=dr){
        int mid=(st+dr)/2;
        if (v[mid]==x) {
            r=mid;
            st=mid+1;
        }
        else if(v[mid]<x) {
            st=mid+1;
        }
        else {
            dr=mid-1;
        }
    }
    return r;
}
int BSR(long long x) {
    int st=1, dr=N, r=-1;
    while (st<=dr) {
        int mid=(st+dr)/2;
        if (v[mid]<=x) {
            r=mid;
            st=mid+1;
        }
        else {
            dr=mid-1;
        }
    }
    return r;
}

int BSL(long long x) {
    int st=1, dr=N, r=-1;
    while (st<=dr) {
        int mid=(st+dr)/2;
        if (v[mid]>=x) {
            r=mid;
            dr=mid-1;
        }
        else {
            st=mid+1;
        }
    }
    return r;
}

int main() {
    cin>>N;

    for (int i = 1; i <= N; i++)
        cin>>v[i];
    int M;
    cin>>M;
    while (M--) {
        int tip;
        long long x;
        cin>>tip>>x;
        if(tip==0)
            cout<<cautare0(x)<<"\n";
        else if(tip==1)
            cout<<BSR(x)<<"\n";
        else
            cout<<BSL(x)<<"\n";
    }

    return 0;
}