#include <stdio.h>

using namespace std;

int v[100001],poz,x,ok;

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

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

    return 0;
}