#include <bits/stdc++.h>
#define oo 500005
using namespace std;

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

int n, caz, m, v[100005], poz, x;

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

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

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


int main(){
    in>>n;
    for(int i = 1; i <= n; i++)
        in>>v[i];
    in>>m;
    for(int i = 1; i <= m; i++){
        in>>caz>>x;
        if(!caz)
            out<<cautbin()<<"\n";
        else
            if(caz == 1)
                out<<cautbin1()<<"\n";
        else
            out<<cautbin2()<<"\n";
    }
}