#include <cstdio>
#include <fstream>

using namespace std;

int n,m;
int a[100005];

int b_search0(int x)
{
    int i,step=1;
    while (step<n) step<<=1;

    for(i=1;step;step>>=1)
    {
        if (i+step<=n && a[i+step]<=x) i+=step;
    }
    if (a[i]!=x) return -1;
    return i;
}

int b_search1(int x)
{
    int i,step=1,maxim=1;
    while(step<n) step<<=1;

    for (i=1;step;step>>=1)
        if (i+step<=n && a[i+step]==x) i+=step;
        else if (i+step<=n && a[i+step]<x) {i+=step; maxim=i;}
    if (a[i]==x) return i;
    return maxim;
}
int b_search2(int x)
{
    int i,step=1,minim=n+1;
    while(step<n) step<<=1;

    for(i=1;step;step>>=1)
        if(i+step<=n && a[i+step]==x) minim=i+step;
        else if (i+step<=n && a[i+step]<x) i+=step;
    if (i==1 && minim==n+1) return 1;
    if (a[i]!=x) return i+1;
    return minim;
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    int cod,x;

    scanf("%d",&n);
    for (int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for (int i=0;i<m;++i)
    {
        scanf("%d %d",&cod,&x);
        if (cod==0) printf("%d\n",b_search0(x));
        else if (cod==1) printf("%d\n",b_search1(x));
        else if (cod==2) printf("%d\n",b_search2(x));
    }
    return 0;
}