#include <fstream>
#include <iostream>
#define fin "cautbin.in"
#define fou "cautbin.out"
using namespace std;
long sir[100001];
int n,m;

int cbin(int st,int dr,long x)
{
    if(st>dr) return 0;
    int p=(st+dr)/2;
    if(x==sir[p]) return p;
    else if(x>sir[p]) cbin(p+1,dr,x);
         else cbin(st,p-1,x);
}

int main()
{
    ifstream t1(fin);
    ofstream t2(fou);
    int i,j,mod,val,poz,ok;
    t1>>n;
    for(i=1;i<=n;i++) t1>>sir[i];
    t1>>m;
    for(i=1;i<=m;i++)
    {
        t1>>mod>>val;
        if(mod==0)
        {
            poz=cbin(1,n,val);
            if(poz==0) t2<<"-1"<<'\n';
            else
            {
                while(sir[poz]==val) poz++;
                poz--;
                t2<<poz<<'\n';
            }
        }

        if(mod==1)
        {
            poz=cbin(1,n,val);
            if(poz==0) ok=0;
            else ok=1;
            while(ok==0)
            {
                val--;
                poz=cbin(1,n,val);
                if(poz!=0) ok=1;
            }
            while(sir[poz]==val) poz++;
            poz--;
            t2<<poz<<'\n';
        }

        if(mod==2)
        {
            poz=cbin(1,n,val);
            if(poz==0) ok=0;
            else ok=1;
            while(ok==0)
            {
                val++;
                poz=cbin(1,n,val);
                if(poz!=0) ok=1;
            }
            while(sir[poz]==val) poz--;
            poz++;
            t2<<poz<<'\n';
        }

    }
    t2.close();
    t2.close();
    return 0;
}