#include <cstdio>

using namespace std;

int n, a[100005],m;

int cautbin1(int x)
{
    int st, dr;
    int mij=(1+m)/2;
    int poz=-1;
    for(st=1,dr=n;st<=dr;)
    {
        mij=(st+dr)/2;
        if(a[mij]<=x)
        {
            if(a[mij]==x)
                poz=mij;
            st=mij+1;
        }
        else if(a[mij]>x)
            dr=mij-1;
    }

    return poz;
}

int cautbin2(int x)
{
    int st, dr;
    int mij=(1+m)/2;
    int poz=-1;
    for(st=1,dr=n;st<=dr;)
    {
        mij=(st+dr)/2;
        if(a[mij]<=x)
        {
            poz=mij;
            st=mij+1;
        }
        else if(a[mij]>x)
            dr=mij-1;
    }

    return poz;
}

int cautbin3(int x)
{
    int st, dr;
    int mij=(1+m)/2;
    int poz=-1;
    for(st=1,dr=n;st<=dr;)
    {
        mij=(st+dr)/2;
        if(a[mij]>=x)
        {
            poz=mij;
            dr=mij-1;
        }
        else if(a[mij]<x)
            st=mij+1;
    }

    return poz;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    scanf("%d\n", &n);
    for(int i=1;i<=n;i++)
        scanf("%d ", &a[i]);
    scanf("%d\n", &m);
    for(int i=1;i<=m;i++)
    {
        int cer, nr;
        scanf("%d %d\n", &cer, &nr);
        if(cer==0)
            printf("%d\n", cautbin1(nr));
        else if(cer==1)
            printf("%d\n", cautbin2(nr));
        else printf("%d\n", cautbin3(nr));
    }

    return 0;
}