#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
ll i,j,mod=1e9+7, oo=1e18+1;
double const pi=3.14159265;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
ll n,m,t,k;
ll a[1000005];
ll bin0(ll l,ll r,ll x){
    if(r<l) return -1;
    ll mid=l+(r-l)/2;
    if(a[mid]==x&&(mid==n|| a[mid+1]>x)) return mid;
    else if(a[mid]==x&&a[mid+1]==x) return bin0(mid+1,r,x);
    else if(a[mid]<x) return bin0(mid+1,r,x);
    else if(a[mid]>x) return bin0(l,mid-1,x);
}
ll bin1(ll l,ll r,ll x){
    ll mid=l+(r-l)/2;
    if(a[mid]<=x&&(mid==n||a[mid+1]>x)) return mid;
    else if(a[mid]<=x) return bin1(mid+1,r,x);
    else if(a[mid>x]) return bin1(l,mid-1,x);
}
ll bin2(ll l,ll r,ll x){
    ll mid=l+(r-l)/2;
    if(a[mid]>=x&&(mid==1||a[mid-1]<x)) return mid;
    else if(a[mid]>=x) return bin2(l,mid-1,x);
    else if(a[mid]<x) return bin2(mid+1,r,x);
}
int32_t main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    cin>>m;
    for(i=1;i<=m;i++){
        ll tip;
        cin>>tip;
        if(tip==0){
            ll x;
            cin>>x;
            ll ans=bin0(1,n,x);
            cout<<ans<<"\n";
        }
        else if(tip==1){
            ll x;
            cin>>x;
            ll ans=bin1(1,n,x);
            cout<<ans<<"\n";

        }
        else {
            ll x;
            cin>>x;
            ll ans=bin2(1,n,x);
            cout<<ans<<"\n";

        }
    }

    return 0;
}