#include <iostream>
#include <cstdio>
using namespace std;

int n,m,a[100001],x,op;

int caut0(int i,int j)
{
    int m;
    while (i<=j)
    {
        m=(i+j)/2;
        if (a[m]<=x)
            i=m+1;
        else
            j=m-1;
    }
    m=(i+j)/2;

    if (a[m]>x)
        --m;
    if (a[m]==x)
        return m+1;
    return -1;
}

int caut1(int i,int j)
{
    int m;
    while (i<=j)
    {

        m=(i+j)/2;
        if (a[m]<=x)
            i=m+1;
        else
            j=m-1;
    }
    m=(i+j)/2;
    if (a[m]>x)
        --m;
    return m+1;
}
int caut2(int i,int j)
{
    int m;
    while (i<=j)
    {
        m=(i+j)/2;
        if (a[m]<x)
            i=m+1;
        else
            j=m-1;
    }
    m=(i+j)/2;
    if (a[m]<x)
        ++m;
    return m+1;
}

void citire()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for (int i=0;i<n;++i)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    while(m)
    {
        m--;
        scanf("%d%d",&op,&x);
        if (op==0)
            printf("%d\n",caut0(0,n-1));
        if (op==1)
            printf("%d\n",caut1(0,n-1));
        if (op==2)
            printf("%d\n",caut2(0,n-1));
    }
}
int main()
{
    citire();
    return 0;
}