#include<fstream>
using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int a[100001], n, m;

int CautBin0(int x){
    int st = 1, dr = n, p = -1;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(a[mij] == x){
            if(p < mij)
                p = mij;
            st = mij + 1;
        }
        else if(a[mij] > x)
            dr = mij - 1;
        else
            st = mij + 1;
    }
    return p;
}

int CautBin1(int x){
   int st = 1, dr = n, p = -1;
   while(st <= dr){
      int mij = (st + dr) / 2;
      if(a[mij] <= x){
         if(mij > p)
            p = mij;
         st = mij + 1;
      }
      else
        dr = mij - 1;
   }
   return p;
}

int CautBin2(int x){
   int st = 1, dr = n, p = 1000000;
   while(st <= dr){
      int mij = (st + dr) / 2;
      if(a[mij] >= x){
         if(mij < p)
            p = mij;
         dr = mij - 1;
      }
      else
        st = mij + 1;
   }
   return p;
}

int main(){

   cin >> n;
   for(int i = 1; i <= n; ++i)
      cin >> a[i];

   cin >> m;
   for(int i = 1; i <= m; ++i){
       int tip, x;
       cin >> tip >> x;
       if(!tip) /// cea mai mare pozitie pe care se afla x
          cout << CautBin0(x) << '\n';
       else if(tip == 1) /// c.m.p val <= x
          cout << CautBin1(x) << '\n';
       else
          cout << CautBin2(x) << '\n';
   }

   return 0;
}