#include <bits/stdc++.h>
using namespace std;
int x,test,a[100001],m,step,n;

int bs1(int x)
{
    int i,step;
    for(step=1;step<n;step <<= 1);
        for(i=0;step;step >>= 1)
            if(step+i < n && a[step+i] <= x)
                i+=step;

    if(test==0){
        if(a[i] == x ) return i;
        else return -1;
    }
    else if(test==1)
        return i;

}
int bs2(int x)
{
    int i,step;
    for(step=1;step<n;step <<= 1);
        for(i=n;step;step >>= 1)
            if(i-step < n && a[i-step] >= x)
                i-=step;

    return i;

}

void date()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
}
int main()
{
    date();

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

    scanf("%d",&m);
    while(m--)
    {
        scanf("%d %d",&test,&x);

        if(test==0)
            printf("%d\n",bs1(x));
        else if(test==1)
            printf("%d\n",bs1(x));
        else
            printf("%d\n",bs2(x));
    }
    return 0;
}