#include <fstream>
#include <iostream>
#define nmax 100005
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int a[nmax],b[nmax],c[nmax],n,m;
int main()
{   int i,j;
    bool g;
    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)
            {g=false;
             for(j=n;j>=1;j--)
                if(c[i]==a[j]) {g=true; break;}
             if(g==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;
}