#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int v[100005];
int cer0(int x, int st, int dr)
{
    if (st==dr)
        if (v[st]==x)
            return st;
        else
            return -1;
    int mid=(st+dr)/2+1;
    if (v[mid]<=x)
        return cer0(x,mid,dr);
    return cer0(x,st,mid-1);
}
int cer1(int x, int st, int dr)
{
    if (st==dr)
        return st;
    int mid=(st+dr)/2+1;
    if (v[mid]<=x)
        return cer1(x,mid,dr);
    return cer1(x,st,mid-1);
}
int cer2(int x, int st, int dr)
{
    if (st==dr)
        return st;
    int mid=(st+dr)/2+1;
    if (v[mid-1]>=x)
        return cer1(x,st,mid-1);
    return cer1(x,mid,dr);
}
int main()
{
    int n, m;
    cin>>n;
    for (int i=1; i<=n; i++)
        cin>>v[i];
    cin>>m;
    int c, x;
    for (int i=1; i<=m; i++)
    {
        cin>>c>>x;
        if (c==0)
            cout<<cer0(x,1,n)<<'\n';
        else
            if (c==1)
                cout<<cer1(x,1,n)<<'\n';
            else
                cout<<cer2(x,1,n)<<'\n';
    }
    return 0;
}