#include <fstream>
#include <vector>
#include <algorithm>

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

const int MAXN= 100003, MAXM = 100003;
int n,m;
int *v;
int bs0(int be, int length, int x)
{
    int lt = be, rt = length-1,mid;

    while( (rt -lt)> 1)
    {
        mid = lt+(rt-lt)/2;
        if(x >= v[mid])
            lt = mid;
        else
            rt = mid-1;
    }
    if(v[lt] !=x && v[rt]!= x)
        return -1;
    if(v[lt+1] == x)
        lt++;
    return lt;
}
int bs1(int be, int length, int x)
{
    int lt = be, rt = length-1,mid;

    while(  (rt -lt)> 1)
    {
        mid = lt+(rt-lt)/2;
        if(v[mid] <= x)
            lt = mid;
        else
            rt = mid-1;
    }
    if(v[lt+1] <= x)
        lt++;
    return lt;
}
int bs2(int be, int length, int x)
{
    int lt = be, rt = length-1,mij;
    while((rt -lt)> 1)
    {
        mij = lt+(rt-lt)/2;
        if (v[mij]>=x)
            rt = mij;
        else
            lt = mij+1;
    }
    if(v[lt]<x)
        lt++;
    return lt;
}
int main()
{

    in >> n;
    v = new int[n+1];
    for(int i = 0 ; i < n ; i ++)
        in >> v[i];
    in >> m;
    int operatie,x;
    int res;
    for(int i = 0 ; i < m ; i++)
    {
        in >> operatie>> x;

        switch(operatie)
        {
            case 0 : res = bs0(0,n,x);
             if(res == -1)
                out<<res<<'\n';
            else
                out << res+1<<'\n'; break;
            case 1 : out<<bs1(0,n,x)+1<<'\n';break;
            case 2 :out <<bs2(0,n,x)+1<<'\n';break;

        }
    }

    return 0;
}