#include <iostream>
#include <fstream>
#define nmax 100001
using namespace std;

int mid,n,k,i,m,v[nmax],x;

void cautbin(int x, int lo, int hi){
    while (hi-lo>1){
        mid=lo+(hi-lo)/2;
        if (v[mid]>=x) lo=mid;
        else hi=mid;
    }
    if (v[mid]==x) out << mid << "\n";
    else out << "-1" << "\n";
}

void cautbin1(int x, int lo, int hi){
    while (hi-lo>1){
        mid=lo+(hi-lo)/2;
        if (v[mid]<=x) lo=mid;
        else hi=mid;
    }
    out << mid << "\n";
}

void cautbin2(int x, int lo, int hi){
    while (hi-lo>1){
        mid=lo+(hi-lo)/2;
        if (v[mid]>=x) hi=mid;
        else lo=mid;
    }
    out << mid << "\n";
}

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

    in >> n;

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

    in >> k;

    for (i=1; i<=k; i++){
        in >> m >> x;
        if (m==0) cautbin(x,1,n);
        else if (m==1) cautbin1(x,1,n);
        else cautbin2(x,1,n);
    }

    return 0;
}