#include <cstdio>

using namespace std;

int n,a[100005],m,x,c;

int c0_1(int l, int x, int tip)
{
    int i;
    for(l, i=0;l;l>>=1)
        if(i + l <= n && a[i + l] <= x)
            i+=l;
    if(a[i]!=x && tip==0)
        return -1;
    return i;
}
int c2(int l, int x)
{
    int i;
    for(l, i=n;l;l>>=1)
        if(i - l >0 && a[i - l] >= x)
            i-=l;
    return i;
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int lg;
    for(lg=1; lg<=n; lg<<=1);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&c,&x);
        if(c==0||c==1)
            printf("%d\n",c0_1(lg,x,c));
        if(c==2)
            printf("%d\n",c2(lg,x));
    }

    return 0;
}