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

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

int cautareBinara(int i, int j, int x)
{
    int mij = (i+j) / 2;
    if(v[mij] == x)
        return mij;
    else if(v[mij] < x)
        return cautareBinara(i, mij-1, x);
    return cautareBinara(mij+1, j, x);
}

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

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

}

int nr2(int v[], int x)
{
    int poz = cautareBinara(1, n, x);
    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';
        }
    }
}