#include <iostream>
/*0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat */
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int main()
{
   int n, m, v[100000], i, c, maxx, p, st, dr,x,mi;
   f>>n;
   for(i=1; i<=n; i++)
        f>>v[i];
   f>>m;
   for(i=1; i<=m; i++)
   {
       f>>p>>x;
       if(p==0) {
        maxx=-1;
       st=1;
       dr=n;
       while(st<=dr)
       {
           mi=(st+dr)/2;
           if(v[mi]==x) {maxx=mi;
                         if(v[mi+1]==x) st=mi+1;
                         else break;


                        }

           else if(v[mi]>x) dr=mi-1;
               else st=mi+1;
       }
        g<<maxx<<endl;

       }

       else if(p==1)
       {
           maxx=-1;
       st=1;
       dr=n;
       while(st<=dr)
       {
           mi=(st+dr)/2;
           if(v[mi]<=x) {maxx=mi;
                        if(v[mi-1]<=x) st=mi+1;
                        else break;}
           else dr=mi-1;

       }
    g<<maxx<<endl;

       }
       else {
       maxx=-1;
       st=1;
       dr=n;
       while(st<=dr)
       {
           mi=(st+dr)/2;
           if(v[mi]>=x) {maxx=mi;
                        if(v[mi-1]>=x) dr=mi-1;
                        else break;}
           else st=mi+1;

       }
       g<<maxx<<endl;

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



    return 0;
}