#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int s[100010];
int len;
int op0(int param);
int op1(int param);
int op2(int param);

int main()
{
    int nrOp;

    fin >> len;

    for(int i=0; i<len; i++)
    {
        fin >> s[i];
    }

    fin >> nrOp;

    while(nrOp--)
    {
        int op, param;
        fin >> op;
        fin >> param;
        if(op==0)
            fout << op0(param) + 1 << endl;
        else if(op==1)
            fout << op1(param) + 1 << endl;
        else if(op==2)
            fout << op2(param) + 1 << endl;
    }
    return 0;
}
int op0(int param)
{
    if(s[len-1]== param)
    {
        return len-1;
    }
    int lo=0;
    int hi=len-1;
    int mid;
    while(hi-lo > 1)
    {
        mid = lo + (hi-lo)/2;
        if(s[mid] > param)
            hi = mid;
        else lo = mid;
    }
    if(s[hi] == param)
        return hi;
    if(s[lo]==param)
        return lo;
    return -2;
}

int op1(int param)
{
    int lo = 0;
    int hi = len-1;
    int mid;
    while (hi - lo > 1)
    {
        mid = lo + (hi - lo) / 2;
        if (s[mid] > param)
            hi = mid;
        else
            lo = mid;
    }
    if (s[hi] <= param)
        return hi;
    return lo;
}

int op2(int param)
{
    int lo = 0;
    int hi = len-1;
    int mid;
    while (hi - lo > 1)
    {
        mid = lo + (hi - lo) / 2;
        if (s[mid] < param)
            lo = mid;
        else
            hi = mid;
    }

    if (s[lo] >= param)
        return lo;
    return hi;
}