#include <iostream>
#include <fstream>
#include <bitset>
#include <algorithm>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
bitset <100005> c;
int n, v[100005], m, nr, x;

int nr0(int v[], int x)
{
    int poz;
    poz = upper_bound(v+1, v+n+1, x) - v - 1;
    if(v[poz] = x)
    {
        while(v[poz] == x)
            poz++;
        return poz - 1;
    }
    return -1;
}

int nr1(int v[], int x)
{
    int poz = upper_bound(v+1, v+n+1, x) - v - 1;
    while(v[poz] == x)
        poz++;
    return poz - 1;

}

int nr2(int v[], int x)
{
    int poz = upper_bound(v+1, v+n+1, x) - v - 1;
    while(v[poz] == x)
        poz--;
    return poz + 1;
}



int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
        c[v[i]] = 1;
    }

    fin>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>nr>>x;
        if(nr == 0)
            fout<<nr0(v, x)<<'\n';
        else if(nr == 1)
        {
            while(c[x] == 0)
                x--;
            fout<<nr1(v,x)<<'\n';
        }
        else
        {
            while(c[x] == 0)
                x++;
            fout<<nr2(v, x)<<'\n';
        }
    }
}