#include <bits/stdc++.h>
#define N 100000
using namespace std;


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


int n, a[N + 5];
int m;

int CB1(int x)
{
    /// cea mai mare poz pe care apare x, -1 contrar
    int st = 1, dr = n;
    int possible = -1;

    while(st <= dr)
    {
        int mij = (st + dr) /2;
        if(a[mij] == x) possible = mij, st = mij + 1;
        else if(a[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }

    return possible;

}

int CB2(int x)
{
    /// cel mai mare <= x
    int st = 1, dr = n;
    int possible = -1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(a[mij] <= x) possible = mij, st = mij + 1;
        else dr = mij - 1;
    }

    return possible;
}

int CB3(int x)
{
    /// cel mai mic >= x
    int st = 1, dr = n;
    int possible = -1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(a[mij] >= x) possible = mij, dr = mij - 1;
        else st = mij + 1;
    }

    return possible;
}

void Citire()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i];
    fin >> m;
}

void Rezolvare()
{
    int x, op;
    for(int i = 1; i <= m; ++i)
    {
        fin >> op >> x;
        if(op == 0) fout << CB1(x);
        else if(op == 1) fout << CB2(x);
        else fout << CB3(x);
        fout << "\n";
    }
}


int main()
{
    Citire();
    Rezolvare();

    return 0;
}