#include <cstdio>

using namespace std;
const char InFile[]="cautbin.in";
const char OutFile[]="cautbin.out";
const int DIMN=100010;

int n,m,v[DIMN];

int binarySearch(int a,int b,int x)
{
    if(a>=b)
        return a;
    else if(x<v[(a+b)/2])
        return binarySearch(a,(a+b)/2-1,x);
    else if(x==v[(a+b)/2])
        return (a+b)/2;
    else return binarySearch((a+b)/2+1,b,x);
}

int main()
{
    int a,b,t;
    freopen(InFile,"r",stdin);
    freopen(OutFile,"w",stdout);

    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d ",&v[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&a,&b);
        if(a==0)
        {
            t=binarySearch(1,n,b);
            if(b==v[t])
            {
                while(b==v[++t]);
                printf("%d\n",t-1);
            }
            else printf("-1\n");
            continue;
        }
        if(a==1)
        {
            t=binarySearch(1,n,b);
            if(b>=v[t])
            {
                while(b>=v[++t]);
                printf("%d\n",t-1);
            }
            else
            {
                while(b<v[--t]);
                printf("%d\n",t);
            }
            }
            continue;
        }
        if(a==2)
        {
            t=binarySearch(1,n,b);
            if (b<=v[t])
            {
                while(b<=v[--t]);
                printf("%d\n",t+1);
            }
            else
            {
                while(b>v[++t]);
                printf("%d\n",t);
            }
        }

    return 0;
}