#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int n,i,x;
    f>>n;
    int v[n];
    for(i=0;i<n;i++)f>>v[i];
    int m,q,pos,l;
    f>>m;
    for(i=0;i<m;i++)
    {
        f>>q;
        f>>x;
        pos=n/2;
        l=n/2;
        while(l!=1)
        {
            if(v[pos]<x)pos+=l/2;
            else if(v[pos]>x)pos-=l/2;
            else l=1;
            if(l!=1)l/=2;
        }
        if(q==0)
        {
            if(v[pos]!=x)pos=-1;
            else
            {
                while(v[pos]==x)pos++;
                pos--;
            }
        }
        if(q==1)
        {
            while(v[pos]>x)pos--;
            while(v[pos]==x)pos++;
            if(v[pos]>x)pos--;
        }
        if(q==2)
        {
            while(v[pos]<x)pos++;
            while(v[pos]==x)pos--;
            if(v[pos]<x)pos++;
        }
        if(pos!=-1)pos++;
        g<<pos<<'\n';
    }
}