#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("cautbinar.in");
ofstream cout("cautbinar.out");
vector<int> a;
int n;
int cb0(int x)
{
    int st = 1; 
    int dr = n;
    int rez = -1;

    while(st <= dr)
    {
        int mij = (st + dr) >> 1;
        if(a[mij] <= x)
        {
            rez = mij;
            st = mij + 1;

        }
        else{
            dr = mij - 1;
        }
    }
    if (rez == -1 || v[rez] != x) {
        return -1;
    }
    else 
        return rez;
}
int cb1(int x)
{
     int st = 1; 
    int dr = n;
    int rez = -1;

    while(st <= dr)
    {
        int mij = (st + dr) >> 1;
        if(a[mij] <= x)
        {
            rez = mij;
            st = mij + 1;

        }
        else{
            dr = mij - 1;
        }
    }
    if (rez == -1 || v[rez] != x) {
        return -1;
    }
    else
        return rez;
}
int cb2(int x)
{
     int st = 1; 
    int dr = n;
    int rez = -1;
    while(st <= dr)
    {
        int mij = (st + dr) >> 1;
        if(a[mij] >= x)
        {
            rez = mij;
            dr = mij - 1;
        }
        else{
            st = mij + 1;
        }
    }
    if (rez == -1 || v[rez] != x) {
        return -1;
    }
    else 
        return rez;
}
int main ()
{
    cin >> n;
    a.resize(n + 1);
    for(int i = 1; i<=n; i ++)
    {
        cin >> a[i];
    }
    int q;
    cin >> q;
    while(q--)
    {
        short cerr;
        cin >> cerr;
        int x;
        cin >> x;
        if(cerr == 0)
        {
            cout << cb0(x) << '\n';
        }
        else if(cerr == 1)
        {
            cout << cb1(x) << '\n';
        }
        else{
            cout << cb2(x) << '\n';
        }
    }
}
/*

    1 3 3 3 5 
    tre sa caut x
    mij = 3

*/