#include <cstdio>
#define MAXN 100002

using namespace std;

int sir[MAXN],n,m;


inline int caut0(int p,int u,int val)
{
    int m;
    while(p<=u)
    {
        m=(p+u)/2;
        if(sir[m]<=val)
            p=m+1;
        else
            u=m-1;
    }
    m=(p+u)/2;
    if(sir[m]>val)
        m--;
    if(sir[m]==val)
        return m;
    return -1;
}

inline int caut1(int p,int u,int val)
{
   int m;
    while(p<u)
    {
        m=(p+u)/2;
        if(sir[m]<=val)
            p=m+1;
        else
            u=m;
    }
    m=(p+u)/2;
    if(sir[m]>val)
        m--;
    return m;
}

inline int caut2(int p,int u,int val)
{
    int m;
    while(p<u)
    {
        m=(p+u)/2;
        if(sir[m]<val)
            p=m+1;
        else
            u=m;
    }
    m=(p+u)/2;
    if(sir[m]<val)
       m++;
    return m;
}

inline void read()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&sir[i]);
    scanf("%d",&m);
    for(;m;m--)
    {
        int tip,val;
        scanf("%d%d",&tip,&val);
        if(tip==0)
                printf("%d\n",caut0(1,n,val));
        else if(tip==1)
                printf("%d\n",caut1(1,n,val));
            else
                printf("%d\n",caut2(1,n,val));
    }
}


int main()
{
    read();
    return 0;
}