#include <iostream>
#include <cstdio>

using namespace std;

int v[100002],i,n,m,t,x;

int cb0(int x)
{
    int st=1,dr=n,m,p=-1;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]<x)
            st=m+1;
        else if(v[m]>x)
            dr=m-1;
        else
        {
            p=m;
            st=m+1;
        }
    }
    return p;
}

int cb1(int x)
{
    int st=1,dr=n,m,p=-1;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]>x)
            dr=m-1;
        else
        {
            p=m;
            st=m+1;
        }
    }
    return p;
}

int cb2(int x)
{
    int st=1,dr=n,m,p=-1;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]<x)
            st=m+1;
        else
        {
            p=m;
            dr=m-1;
        }
    }
    return p;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    scanf("%d", &n);
    for(i=1;i<=n;i++)
        scanf("%d", &v[i]);
    scanf("%d", &m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d", &t, &x);
        if(t==0)
            printf("%d\n", cb0(x));
        else if(t==1)
            printf("%d\n", cb1(x));
        else
            printf("%d\n", cb2(x));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}