#include <fstream>
using namespace std;
int v[100010];
int bsearch0 (int p ,int u, int x) {
     int mid ;
     
     while (p <= u) {
         mid = (p + u) / 2;
         if (v[mid] <= x)
             p = mid + 1;
         else
             u = mid - 1;
     }
     mid = (p + u) / 2;
     
     if (v[mid] > x) mid --;
     if (v[mid] == x)
        return mid;
return -1;
}
 
int bsearch1 (int p , int u, int x) {
     int mid ;
     
     while (p < u){
         mid = (p + u) / 2;
         if (v[mid] <= x)
             p = mid + 1;
         else
             u = mid;
    }
      
     mid = (p + u) / 2;
     if (v[mid] > x)
         -- mid;
return mid;
}
 
int bsearch2 (int p , int u, int x) {
     int mid ;
     
     while (p < u) {
         mid = (p + u) / 2;
         if (v[mid] < x)
             p = mid + 1;
         else
             u = mid;
    }
     mid = (p + u) / 2;
		 if (v[mid] < x)
             ++ mid;
return mid;
}
 
int main(){
     int i, n, mid, tip, val;
     ifstream fin("cautbin.in");
     ofstream fout("cautbin.out");
     fin>>n;
     for (i = 1; i <= n; ++ i)
         fin>>v[i];
     fin>>mid;
    while (mid--){
         fin>>tip>>val;
          if (tip==0)
             fout<<(bsearch0(1 ,n, val))<<"\n";
          if (tip==1)
             fout<<(bsearch1(1 ,n, val))<<"\n";
          if (tip==2)
             fout<<(bsearch2(1 ,n, val))<<"\n";
    }
return 0;
}