#include <fstream>

using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

long long v[100001];

void read(const int& n)
{
    for(int i=1; i<=n; i++)
        cin>>v[i];
}

int highbin(int st, int dr, const int& x, bool& ap)
{
    int mid, pm=-1;
    ap=true;
    mid=st+(dr-st)/2;
    while(dr>st)
    {
        if(v[mid]==x)
        {
            pm=mid;
            st=mid+1;
            mid=st+(dr-st)/2;
        }
        else if(v[mid]>x)
        {
            st=mid+1;
            mid=st+(dr-st)/2;
        }
        else 
        {
            dr=mid-1;
            mid=st+(dr-st)/2;
        }
        if(st==dr && pm==-1)
        {
            pm=mid;
            ap=false;
        }
    }
    return pm;
}

int lowbin(int st, int dr, const int& x)
{
    int mid, pm=-1;
    mid=st+(dr-st)/2;
    while(dr>st)
    {
        if(v[mid]==x)
        {
            pm=mid;
            dr=mid-1;
            mid=st+(dr-st)/2;
        }
        else if(v[mid]>x)
        {
            st=mid+1;
            mid=st+(dr-st)/2;
        }
        else 
        {
            dr=mid-1;
            mid=st+(dr-st)/2;
        }
    }
    return pm;
}

int main()
{
    int n, m, op, x, r;
    bool flag;
    cin>>n;
    read(n);
    cin>>m;

    for(int i=0; i<m; i++)
    {
        cin>>op>>x;

        if(op==0)
        {
            r=highbin(1, n, x, flag);
            if(!flag)
                cout<<"-1\n";
            else
                cout<<r<<"\n";
        }
        else if(op==1)
        {
            r=highbin(1, n, x, flag);
            if(flag)
                cout<<r<<"\n";
            else
                cout<<r-1<<"\n";
        }
        else
        {
            r=lowbin(0, n, x);
            if(flag)
                cout<<r<<"\n";
            else
                cout<<r+1<<"\n";

        }
    }
}