#include <fstream>
#include <iostream>
#define nmax 100005
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n,m;
int a[nmax],b[nmax],c[nmax];

int main()
{
    int i,ct=0,j,s,d;
    bool gasit,gasit1,gasit2;
    fin>>n;
    for(i=1; i<=n; i++) fin>>a[i];
    fin>>m;
    for(i=1; i<=m; i++) fin>>b[i]>>c[i];
    fin.close();

    for(i=1; i<=m; i++)
        if(b[i]==0)
            {gasit=false;
             for(j=n; j>=1; j--)
                if(c[i]==a[j]) {gasit=true; break;}
             if(gasit==true) fout<<j<<"\n";
             else fout<<-1<<"\n";
            }
        else if(b[i]==1)
                {for(j=n; j>=1; j--)
                    if(a[j]<=c[i]) break;
                 fout<<j<<"\n";
                }
             else
                {for(j=1; j<=n; j++)
                    if(a[j]>=c[i]) break;
                 fout<<j<<"\n";
                }
    fout<<"\n";
    fout.close();
    return 0;
}