#include <fstream>

using namespace std;

int N[100005];

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");

    int st,dr,mid,n,x,i,nr,M;

    f>>n;
    for(i=1;i<=n;i++) f>>N[i];
    f>>M;
    for(i=1;i<=M;i++)  {
      st=1;
      dr=n;
      mid=(st+dr)/2;
      f>>nr>>x;
      if(nr==0)  {
        while(dr-st>1) {
          if(N[mid]<=x) {st=mid; mid=(st+dr)/2;}
          else {dr=mid; mid=(st+dr)/2;}
        }
          if(N[dr]==x) g<<dr;
          else if(N[st]==x) g<<st;
          else g<<-1;
          g<<'\n';
        }
       else if(nr==1) {
          while(dr-st>1) {
          if(N[mid]<=x) {st=mid; mid=(st+dr)/2;}
          else {dr=mid; mid=(st+dr)/2;}
        }
          if(N[dr]==x) g<<dr;
          else g<<st;
          g<<'\n';
       }
        else {
          while(dr-st>1) {
          if(N[mid]>=x) {dr=mid; mid=(st+dr)/2;}
          else {st=mid; mid=(st+dr)/2;}

        }

        if(N[st]>=x) g<<st;
        else g<<dr;
        g<<'\n';
        }
     }

        f.close();
        g.close();
        return 0;
}