#include <cstdio>
using namespace std;
int n, m, a[100001], caz, x;

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

int caz_2(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);
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    scanf("\n");
    int lg;
    for(lg=1; lg<=n; lg<<=1);

    scanf("%d", &m);
    for(int j=1; j<=m; j++)
    {
        scanf("%d %d\n", &caz, &x);
        if(caz!=2)
            printf("%d\n", caz0_1(lg, x, caz));
        else
            printf("%d\n", caz_2(lg, x));
    }
    return 0;
}