#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

const int Nmax = 100005;
int n, M, a[Nmax], x;

void Read()
{
    f>>n;
    for(int i = 1; i <= n; i++) f>>a[i];
}

void Exist()
{
    int s = 1, d = n, m;
    while(s < d)
    {
        m = (s+d)/2;
        if(x >= a[m]) s = m+1;
        else d = m-1;
    }
    m = (s+d)/2;
    if(a[m]!=x) m--;
    if(a[m] == x) g<<m<<'\n';
    else g<<-1<<'\n';
}

void Small()
{
    int s = 1, d = n, m;
    while(s < d)
    {
        m = (s+d)/2;
        if(x >= a[m]) s = m+1;
        else d = m-1;
    }
    m = (s+d)/2;
    if(a[m] > x) m--;
    g<< m<<'\n';
}

void Big()
{
    int s = 1, d = n, m;
    while(s < d)
    {
        m = (s+d)/2;
        if(x > a[m]) s = m+1;
        else d = m-1;
    }
    m = (s+d)/2;
    if(a[m] < x) m++;
    g<< m<<'\n';
}

void SolveAndPrint()
{
    f>>M;
    while(M--)
    {
        int opt;
        f>>opt>>x;
        if(opt == 0) Exist();
        if(opt == 1) Small();
        if(opt == 2) Big();
    }
}

int main()
{
    Read();
    SolveAndPrint();
    return 0;
}