#include <iostream>
#include <fstream>
using namespace std;
int v[100005];
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int cautbin_big(int ls, int ld, int x)
{
    int mij,rez = -1;
    while(ls <= ld)
    {
        mij = (ls + ld) / 2;
        if(v[mij] >= x){
            rez = mij;
            ld = mij -1;
            }
        else
            ls = mij +1;
    }
    return rez;
}
int cautbin_small(int ls, int ld, int x)
{
    int mij ,  rez = -1 ;
    while(ls <= ld)
    {
        mij = (ls + ld) / 2;
        if(v[mij] <= x){
            rez= mij ;
            ls = mij + 1;
            }

        else
            ld = mij - 1;

    }
    return rez;
}

int cautbin_normal(int ls , int ld , int x)
{
    int mij , gasit = -1 ;
    while(ls<=ld )
    {
        mij = (ls+ld)/2;
        if(x < v[mij])
            ld = mij -1;
        else if(x>v[mij])
            ls = mij+1 ;
        else{
            gasit = mij ;
            ls = mij+1;
            }
    }
    return gasit ;
}

int main()
{
    int n, m, i, tip_rezultat, gasit, x;
    f >> n;
    for(i = 1;i <= n;i++)
        f >> v[i];
    f >> m;
    for(i = 1;i <= m;i++)
    {
        f >> tip_rezultat >> x;

        if(tip_rezultat == 0)
        {
            g<< cautbin_normal(1, n, x)<<'\n';

        }
        if(tip_rezultat == 1)
             g<<cautbin_small(1, n, x)<<'\n';
        else if(tip_rezultat == 2)
            g<<cautbin_big(1, n, x)<<'\n';
    }
    return 0;
}