#include <bits/stdc++.h>
#define ll long long
#define sz size
#define pb push_back
#define er erase
#define in insert
#define fr first
#define sc second
#define mp make_pair
#define pi pair
#define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
#define rc(s) return cout<<s,0
const int mod=1e9+7;
const int inf=1e5;
using namespace std;
std::multiset<int>::iterator it;
std::multiset<int>::iterator it1;

int a[100005];
int n,t,m;
int x;

int func0(int l,int r,int x){
      while(l<=r){
        int mid=l+(r-l)/2;
        if(a[mid]<=x) l=mid+1;
        else r=mid-1;
      }
      int mid=l+(r-l)/2;
      if(a[mid]==x) mid++;
      if(a[mid]>x) return mid-1;
      return -1;


}

int func1(int l,int r,int x){
      while(l<=r){
        int mid=l+(r-l)/2;
        if(a[mid]<=x) l=mid+1;
        else r=mid-1;
      }
      int mid=l+(r-l)/2;
      if(a[mid]<=x) mid++;
      if(mid==n+1 || a[mid]>x) return mid-1;

}

int func2(int l,int r,int x){
    while(l<=r){
        int mid=l+(r-l)/2;
        if(a[mid]<x) l=mid+1;
        else r=mid-1;
    }
    int mid=l+(r-l)/2;
    if(a[mid]>=x) mid--;
    if(mid==0 || a[mid]<x) return mid+1;


}

int main(){ _
    ifstream fin ("cautbin.in");
    ofstream fout("cautbin.out");
    fin >> n;
    for(int i=1;i<=n;i++) fin >> a[i];
    fin >> m;
    for(int i=1;i<=m;i++){
        fin >> t >>x;
        if(t==0){ fout<<func0(1,n,x)<<'\n';  continue; }
        if(t==1){ fout<<func1(1,n,x)<<'\n'; continue; }
        if(t==2){ fout<<func2(1,n,x)<<'\n'; continue; }
    }
}