#include <iostream>
#include <fstream>
using namespace std;
int n[100001],N,M,p,i,j,jum,x,t;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main()
{
    f>>N;
    for (i=1; i<=N; i++) f>>n[i];
    jum=N/2;
    f>>M;
    for (i=1; i<=M; i++)
    {
        t=1;
        f>>p>>x;
        if (p==0)
        {
            if (x>=n[jum]) {for (j=N; j>jum; j--) if (x==n[j]) {g<<j<<"\n"; t=0;break; }}
            else {for (j=jum; j>0; j--) if (x==n[j]) {g<<j<<"\n"; t=0;break; }}
            if (t) g<<-1<<"\n";
        }

        else if (p==1)
        {
            if (x>=n[jum]) {for (j=N; j>jum; j--) if (x>=n[j]) {g<<j<<"\n"; break; }}
            else {for (j=jum; j>0; j--) if (x>=n[j]) {g<<j<<"\n"; break; }}
        }
        else if (p==2)
        {
           if (x>=n[jum])  {for (j=1; j<=jum; j++) if (x<=n[j]) {g<<j<<"\n"; break; }}
           else {for (j=jum+1; j<=N; j++) if (x<=n[j]) {g<<j<<"\n"; break; }}

        }
    }
    return 0;
}