#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, m, v[100001];

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

    mij = (st+dr)/2;
    if(v[mij] > x)
        mij--;

    if(v[mij] == x)
        return mij;
    return -1;
}

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

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

int main()
{
    int cb, x;
    fin >> n;
    for(int i=1; i<=n; i++)
        fin >> v[i];
    fin >> m;
    for(int i=1; i<=m; i++)
    {
        fin >> cb >> x;
        if(cb==0)
           fout << CB0(x) << "\n";
        else if(cb==1)
            fout << CB1(x) << "\n";
        else
            fout << CB2(x) << "\n";
    }
    return 0;
}