#include <bits/stdc++.h>
using namespace std;
#define mod                1000000007
#define ll                 long long 
#define all(v)             v.begin(), v.end()
#define fr(n)              for(ll i=0;i<n;++i)
#define ctz(x)             __builtin_ctzll(x)
#define clz(x)             __builtin_clzll(x)
#define pcount(x)          __builtin_popcountll(x)
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
#define cin fin
#define cout fout
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
//const ll maxn = 3e5 + 5;
//int f[maxn],nf[maxn],inv[maxn];
//const int M=998244353;
//void init(){
//inv[1]=1; for (int i=2;i<maxn;i++) inv[i]=M-1ll*(M/i)*inv[M%i]%M;
//f[0]=nf[0]=1; for (int i=1;i<maxn;i++) f[i]=1ll*f[i-1]*i%M,nf[i]=1ll*nf[i-1]*inv[i]%M;
//}
//int C(int x,int y){return 1ll*f[x]*nf[y]%M*nf[x-y]%M;}



void solve(){
    ll n;cin>>n;
    ll v[n];
    fr(n){
        cin>>v[i];
    }
    ll k;cin>>k;
    while(k--){
        ll a,b;cin>>a>>b;
        if(a==0){
            ll ans=-2;
            ll l=0, r=n-1;
            while(l<=r){
                ll mid=(l+r)/2;
                if(v[mid]==b){
                    ans=mid;
                    l=mid+1;
                }
                else{
                    if(v[mid]<b){
                        l=mid+1;
                    }
                    else r=mid-1;
                }
            }
            cout<<ans+1<<"\n";
        }
        else if(a==1){
            ll ans=-2, l=0, r=n-1;
            while(l<=r){
                ll mid=(l+r)/2;
                if(v[mid]<=b){
                    ans=mid;l=mid+1;
                }
                else{
                    r=mid-1;
                }
            }
            cout<<ans+1<<"\n";
        }
        else{
            ll ans=-1, l=0, r=n-1;
            while(l<=r){
                ll mid=(l+r)/2;
                if(v[mid]>=b){
                    ans=mid;r=mid-1;
                }
                else{
                    l=mid+1;
                }
            }
            cout<<ans+1<<"\n";
        }
    }

    
}


int main(){
//    ios_base::sync_with_stdio(false); cin.tie(NULL);
//    ll t;cin>>t;while(t--){solve();cout<<endl;}
    solve();
}