#include <iostream>
#include <fstream>

using namespace std;

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

int n, v[100005];

int cbin0(int x)
{
    int left=1, right=n;
    while(left<=right)
    {
        int m=(left+right)>>1;
        if (v[m]==x&&v[m+1]!=x)
            return m;
        if (v[m]<=x)
        left=m+1;
        else right=m-1;
    }
    return -1;
}

int cbin1(int x)
{
    int left=1, right=n, q;
    while(left<=right)
    {
    int m=(left+right)>>1;
    if (v[m]<=x)
    {
        q=m;
        left=m+1;
    }
    else right=m-1;

    }
    return q;
}

int cbin2(int x)
{
    int left=1, right=n, q;
    while(left<=right)
    {
        int m=(left+right)>>1;
        if (v[m]>=x)
        {
            q=m;
            right=m-1;
        }
        else left=m+1;
    }
    return q;

}

int main()
{
    int p, m, x, i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
        fin>>m;
        while(m>0)
        {
            fin>>p>>x;
            if(p==0)
                fout<<cbin0(x)<<'\n';
            else if (p==1)
                fout<<cbin1(x)<<'\n';
            else fout<<cbin2(x)<<'\n';
            m--;

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