#include <stdio.h>
#define Nmax 100001

using namespace std;

int v[Nmax];

int bsearch0(int p,int u,int x)
{
    int m;

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

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

    while(p<u)
    {
        m=(p+u)/2;
        if(v[m]<x)
            p=m+1;
        else
            u=m;
    }
    m=(p+u)/2;
    if(v[m]<x)
        m++;
    return m;
}
int main()
{
    int n,m,tip,x;

    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    scanf("%d",&n);

    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d",&tip,&x);
        if(tip==0)printf("%d\n",bsearch0(1,n,x));
        if(tip==1)printf("%d\n",bsearch1(1,n,x));
        if(tip==2)printf("%d\n",bsearch2(1,n,x));
    }
}