#include <fstream>
#define in "cautbin.in"
#define out "cautbin.out"
#define N 100003

using namespace std;

ifstream fin(in);
ofstream fout(out);

int n,m,A[N],p,x;

inline int poz_max(const int &val)
{
    int st,dr,mij;
    st = 1,dr = n;
    while(st<=dr)
    {
        mij =(st+dr)/2;

        if(A[mij] <= val)
            st = mij+1;
        else dr = mij-1;
    }

    if(A[st] != val) --st;

    return (A[st] != val ? -1 : st);
}

inline int poz_mm_max(const int &val)
{
    int st,dr,mij;
    st = 1,dr = n;
    while(st<=dr)
    {
        mij =(st+dr)/2;

        if(A[mij] <= val)
            st = mij+1;
        else dr = mij-1;
    }

    if(A[st] > val) --st;

    return st;
}

inline int poz_mm_min(const int &val)
{
    int st,dr,mij;
    st = 1,dr = n;
    while(st<=dr)
    {
        mij = (st+dr)/2;
        if( A[mij] < val)
            st = mij+1;
        else
            dr = mij-1;
    }
    if(A[dr] < val) ++dr;
    return dr;
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; ++i)
        fin>>A[i];
    fin>>m;
    while(m--)
    {
        fin>>p>>x;
        if(p == 0) fout<<poz_max(x);
        else if(p == 1) fout<<poz_mm_max(x);
        else fout<<poz_mm_min(x);
        fout<<"\n";
    }

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