#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)
    {
        if(v[st] > val)st--;
        return v[st] == val ? st : -1;
    }
    else
    {
        int mid = st + (dr - st)/2;
        if(val < v[mid])return cauta0(st,mid-1,val);
        else return cauta0(mid+1,dr,val);
    }
}

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

        if(v[mid] <= val)return cauta1(mid+1,dr,val);
        else return cauta1(st,mid,val);
    }
}

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

        if(v[mid] >= val)return cauta2(st,mid,val);
        else return cauta2(mid+1,dr,val);
    }
}

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)
        printf("%d\n",cauta0(1,n,b));
        else
        if(a == 1)
        printf("%d\n",cauta1(1,n,b));
        else
        printf("%d\n",cauta2(1,n,b));
    }
}

int main()
{
    citire();

    return 0;
}