#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;
    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++)
        {gasit=false; s=1; d=n;
             while(s<=d && gasit==false)
                {m=(s+d)/2;
                 if(m==c[i]) gasit=true;
                 else if(c[i]<a[m]) d=m-1;
                      else s=m+1;
                }
         if(b[i]==0)
             if(gasit==false) fout<<-1<<"\n";
             else
                {for(j=n; j>=1; j--)
                    if(c[i]==a[j]) break;
                 fout<<j<<"\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;
}