#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=0; 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+1<<"\n";
        }
        else if(op==2)
        {
            r=highbin(0, n, x, flag);
            if(r==0)
                cout<<"0\n";
            else
                cout<<r<<"\n";
        }
        else
        {
            r=highbin(0, n, x, flag);
            if(r==n)
                cout<<r<<"\n";
            else
                cout<<r+2<<"\n";
        }
    }
}