#include <iostream>
#include <fstream>

using namespace std;

int n, a[100005],logaN;

int cautbin1 (int x)
{
    int step, i;
    for (i=0, step=logaN ;step;step >>= 1)
        if (step+i<=n&&a[step+i]<=x)
            i+=step;
    return i;
}

int cautbin2 (int x)
{
    int step, i;
    for (i=n, step=logaN;step;step >>= 1)
        if (i-step>0 && a[i-step]>=x)
            i-=step;
    return i;
}

int main()
{
    int m, c, val;
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");
    fin>>n;
    for (int i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for (logaN=1;logaN<=n;logaN <<= 1);
    for (int i=0;i<m;i++)
    {
        fin>>c>>val;
        if (c==0)
        {
            int y=cautbin1(val);
            if(a[y]!=val)
                fout<<"-1\n";
            else
                fout<<y<<"\n";
        }
        else if (c==1)
            fout<<cautbin1(val)<<"\n";
        else
            fout<<cautbin2(val)<<"\n";
    }
    return 0;
}