#include <iostream>
#include <cstdio>
using namespace std;
int v[100002],poz;

void cb(int st, int dr, int t)
{
    int m=(st+dr)/2;
    if(st>dr) return;
    poz=m;
    if(v[m]==t) return;
    else if(v[m]>t) cb(m+1,dr,t);
    else cb(st,m-1,t);
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int n,i,j,t,p;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",v+i);
    scanf("%d",&p);
    for(i=0;i<p;i++)
    {
        scanf("%d%d",&j,&t);
        cb(1,n,t);
        if(j==0)
        {
            if(v[poz]==t) {while(v[poz+1]==t)poz++; printf("%d\n",poz);}
            else printf("-1\n");
        }
        else if(j==1)
        {
            if(v[poz]!=t)
            {
                if(v[poz]>t) poz--;
                printf("%d\n",poz);
            }
            else
            {
                while(v[poz+1]==t)poz++; printf("%d\n",poz);
            }
        }
        else
        {
            if(v[poz]!=t)
            {
                if(v[poz]<t) poz++;
                printf("%d\n",poz);
            }
            else
            {
                while(v[poz-1]==t)poz--; printf("%d\n",poz);
            }
        }
    }

    return 0;
}