#include <iostream>
#include <cstdio>
#define Nmax 100000
using namespace std;

int v[Nmax];
int mod0(int s,int f,int x)
{
    int m;
    while(s<=f)
    {
        m=(s+f)/2;
        if(v[m]<=x)
            s=m+1;
        else
            f=m-1;
    }
    m=(s+f)/2;
    if(v[m]>x)m--;
    if(v[m]==x)
        return m;
    return -1;
}
int mod1(int s,int f,int x)
{
    int m;
    while(s<f)
    {
        m=(s+f)/2;
        if(v[m]<=x)
            s=m+1;
        else
            f=m;
    }
    m=(s+f)/2;
    if(v[m]>x)
      --m;
    return m;
}
int mod2(int s,int f,int x)
{
    int m;
    while(s<f)
    {
        m=(s+f)/2;
        if(v[m]<x)
            s=m+1;
        else
            f=m;
    }
    m=(s+f)/2;
    if(v[m]<x)
        ++m;
    return m;
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int n,x,k,nr;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    scanf("%d",&nr);
    for(int i=1;i<=nr;i++)
        {scanf("%d%d",&k,&x);
        if(k==0)
        printf("%d\n",mod0(1,n,x));
        if(k==1)
        printf("%d\n",mod1(1,n,x));
        if(k==2)
        printf("%d\n",mod2(1,n,x));
        }

}