#include <fstream>
#include <algorithm>

using namespace std;


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

int v[100000];

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

void T0(const int& n, const int& x)
{
    int poz=upper_bound(v, v+n, x)-v-1;
    //cout<<v[poz]<<" ";
    if(v[poz]==x)
        cout<<poz+1<<"\n";
    else
        cout<<-1<<"\n";
}

void T1(const int& n, const int& x)
{
    if(binary_search(v, v+n, x))
        T0(n, x);
    else
    {
        int poz=lower_bound(v, v+n, x)-v;
        cout<<poz<<"\n";
    }
}

void T2(const int& n, const int& x)
{
    if(binary_search(v, v+n, x))
        cout<<lower_bound(v, v+n, x)-v+1<<"\n";
    else
        cout<<upper_bound(v, v+n, x)-v+1<<"\n";
}

int main()
{
    ios::sync_with_stdio(false);
    
    int n, m;
    cin>>n;
    readArray(n);

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

        if(type==0)
        {
            T0(n, x);
        }
        else if(type==1)
        {
            T1(n, x);
        }
        else
            T2(n, x);
    }
}