#include <iostream>
#include <fstream>
using namespace std;

//char buff[400032];
int a[100001];
int n,q,x,tip;

int bin0(int x)
{
    int step,i;

    for(step=1; step<=n; step<<=1);
    for(i=0; step ; step>>=1)
    {
        if(i+step<n && a[i+step]<=x)
            i=i+step;
    }
    if(a[i]==x)
        return i;
    else
        return -1;
}

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

int bin2(int x)
{
    int step,i;
    for(step=1;step<n; step <<=1);
    for(i=step; step; step>>=1)
    {
        if(i-step>0 && a[i-step]>=x)
            i=i-step;
    }
    return i;
}
int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");

    in >> n;
    for(int i=1;i<=n;i++)
        in >> a[i];
    in >> q;
    for(int i=0;i<q;i++)
    {
        in >> tip >> x;
        if(tip==0)
           out <<  bin0(x) << "\n";
        else if(tip==1)
           out <<  bin1(x) << "\n";
        else
            out << bin2(x) << "\n";
    }
    return 0;
}