#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;

//ifstream f ("cautbin.in");
//ofstream g ("cautbin.out");

int v[NMAX],n,m;

int cauta0(int st,int dr,int val)
{
    if(st > dr)
    {
        st--;
        return v[st] == val?st:-1;
    }
    else
    {
        int mid = st + (dr - st)/2;
        if (val >= v[mid])cauta0(mid+1,dr,val);
        else return cauta0(st,mid-1,val);
    }
}

int cauta1(int st,int dr,int val)
{
    if(st > dr)
    {
        st--;
        return st;
    }
    else
    {
        int mid = st + (dr - st)/2;
        if(val >= v[mid])return cauta1(mid+1,dr,val);
        else return cauta1(st,mid-1,val);
    }
}

int cauta2(int st,int dr,int val)
{
    if(st > dr)
    {
        return st;
    }
    else
    {
        int mid = st + (dr - st)/2;
        if(val <= v[mid])return cauta2(st,mid-1,val);
        else return cauta2(mid+1,dr,val); // if (val > v[mid] )
    }
}


void citire()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&v[i]);

    int a,b;
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&a,&b);
        if(a == 0)
        {
            //cout << cauta0(1,n,b);
            printf("%d\n",cauta0(1,n,b));
        }
        else
        if(a == 1)
        {
          //  cout << cauta1(1,n,b);
            printf("%d\n",cauta1(1,n,b));
        }
        else
        {
//            cout << cauta2(1,n,b);
            printf("%d\n",cauta2(1,n,b));
        }
    }
}

int main()
{
    citire();

    return 0;
}