#include <iostream>
#include <fstream>

using namespace std;

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

#define limn 100010
int n,v[limn];

/// cea mai mare pozitie pe care se afla un element cu valoarea x
/// sau -1 daca aceasta valoare nu se gaseste in sir
int q0(int x)
{
    int pos, mask;
    for(mask=1; mask<=n; mask<<=1);
    mask>>=1;
    pos = 0;
    for(;mask;mask>>=1)
        if(pos+mask<=n && v[pos+mask]<=x)
            pos+=mask;
    if(v[pos]==x)   return pos;
    return -1;
}

/// cea mai mare pozitie pe care se afla un element
/// cu valoarea mai mica sau egala cu x in sir
int q1(int x)
{
    int pos, mask;
    for(mask=1; mask<=n; mask<<=1);
    mask>>=1;
    pos = 0;
    for(;mask;mask>>=1)
        if(pos+mask<=n && v[pos+mask]<=x)
            pos+=mask;
    return pos;
}

/// cea mai mica pozitie pe care se afla un element
/// cu valoarea mai mare sau egala cu x in sir
int q2(int x)
{
    int pos, mask;
    for(mask=1; mask<=n; mask<<=1);
    mask>>=1;
    pos = n;
    for(;mask;mask>>=1)
        if(pos-mask>0 && v[pos-mask]>=x)
            pos-=mask;
    return pos;
}

int main()
{
    int nrq,qtype,x;
    fin>>n;
    for(int i=1; i<=n; i++) fin>>v[i];
    fin>>nrq;
    while(nrq--)
    {
        fin>>qtype>>x;
        if(qtype==0)    fout<<q0(x)<<'\n';
        else if(qtype==1)   fout<<q1(x)<<'\n';
        else fout<<q2(x)<<'\n';
    }

    fin.close();
    fout.close();
    return 0;
}