#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <fstream>
#define ll long long
using namespace std;

int v[100010];
int n;

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

int cb0(int x)
{
    int st = 1;
    int dr = n;
    int mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] <= x)
            st = mij + 1;
        else
            dr = mij - 1;
    }
    if(v[mij] > x) mij--;
    if(v[mij] == x)
        return mij;
    return -1;
}

int cb1(int x)
{
    int st = 1;
    int dr = n;
    int mij;
    while(st < dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] <= x)
            st = mij + 1;
        else
            dr = mij;
    }
    mij = (st + dr) / 2;
    if(v[mij] > x)
        mij--;
    return mij;
}

int cb2(int x)
{
    int st = 1;
    int dr = n;
    int mij;
    while(st < dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] < x)
            st = mij + 1;
        else 
            dr = mij;
    }
    mij = (st + dr) / 2;
    if(v[mij] > x)
        mij++;
    return mij;
}

int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> v[i];
    int m;
    f >> m;
    for(int i = 0; i < m; ++i)
    {
        int x, y;
        f >> x >> y;
        if(x == 1) g << cb1(y) << '\n';
        else if(x == 0) g << cb0(y) << '\n';
        else g << cb2(y) << '\n';
    }
    return 0;
}