#include <fstream>
#include <algorithm>

using namespace std;
int v[100000];
ifstream in("cautbin.in");
ofstream out("cautbin.out");

//cea mai mare pos gasita a unui numar egal cu val
int cbin0(int val, int n)
{
    int pos=0;
    int foundpos = -2;
    if(v[0]==val) foundpos=0;
    for(int msk=1<<20; msk>0; msk/=2)
        if(pos+msk<n && v[pos+msk]<=val){
            pos += msk;
            if(v[pos]==val)
                foundpos = pos;

        }
    return foundpos;
}

//cea mai mare pos gasita a unui numar mai mic sau egal decat val
int cbin1(int val, int n)
{
    int pos=0;
    for(int msk=1<<20; msk>0; msk/=2)
        if(pos+msk<n && v[pos+msk]<=val)
            pos += msk;
    return pos;
}

//cea mai mica pos gasita a unui numar mai mare sau egal decat val
int cbin2(int val, int n)
{
    int pos=0;
    int foundpos = n-1;
    if(v[0]>=val) return 0;
    for(int msk=1<<20; msk>0; msk/=2)
        if(pos+msk<n && v[pos+msk]>=val)
            foundpos = pos+msk;
        else if(pos+msk<n && v[pos+msk]<val)
            pos += msk;
    return foundpos;
}

int main()
{
    int n, nr, intrebari, m;
    in >> n;

    for(int i=0; i<n; i++)
        in >> v[i];
    in >> intrebari;

    for(int i=0; i<intrebari; i++)
    {
        in >> m >> nr;
        if(m==0)
            out << cbin0(nr, n)+1 << '\n';
        else if(m==1)
            out << cbin1(nr, n)+1 << '\n';
        else
            out << cbin2(nr, n)+1 << '\n';
    }
    return 0;
}