#include <cstdio>

using namespace std;
int n, a[100001], m, tip, x;
int lg, log;

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

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

}

int tip2(int lg, int x)
{
    int i;
    for(i=n; lg!=0; lg>>=1)
        if(i - lg > 0 && a[i-lg] >= x)
            i-=lg;
    return i;
}
int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    cit();
    for(lg=1; lg <=n; lg<<=1);

    scanf("%d\n", &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d\n", &tip, &x);
        if(tip < 2)
            printf("%d\n", tip01(lg, x));
        else printf("%d\n", tip2(lg, x));
    }
    return 0;
}