#include <stdio.h>

using namespace std;

int v[100001],poz,x;

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

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

    return 0;
}