#include <cstdio>

using namespace std;
int i,j,x,y,s,nr,k,n,m,a[100002];
int bins0(int s,int d,int x)
{
    int m;
    m=(s+d)/2;
    while(s<d)
    {
        if(a[m]>x) d=m-1;
        while(a[m]==x)
        {
            m++;
            if(a[m]!=x) return m-1;
        }
        if(a[m]<x) s=m+1;
        m=(s+d)/2;
    }
    return -1;
}
int bins1(int s,int d,int x)
{
    int m;x++;
    bool ok=true;
    m=(s+d)/2;
    while(ok)
    {
        x--;
    while(s<d)
    {
        if(a[m]<x) s=m+1;
        if(a[m]>x) d=m-1;
        while(a[m]==x)
        {
            m++;
            if(a[m]!=x)
           return m-1;
        }
        m=(s+d)/2;
    }
    }
}
int bins2(int s,int d,int x)
{
    int m;x--;
    bool ok=true;
    m=(s+d)/2;
    while(ok)
    {
        x++;
    while(s<d)
    {
        if(a[m]<x) s=m+1;
        if(a[m]>x) d=m-1;
        while(a[m]==x)
        {
            m--;
            if(a[m]!=x)
           return m+1;
        }
        m=(s+d)/2;
    }
    }
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d\n",&n);
    for(i=1; i<=n; i++)
    scanf("%d ",&a[i]);
    scanf("%d\n",&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d",&x,&y);
        if(x==0) printf("%d\n",bins0(1,n,y));
        if(x==1) printf("%d\n",bins1(1,n,y));
        if(x==2) printf("%d\n",bins2(1,n,y));

    }
    return 0;
}