#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <pi, pi>
#define vi vector <int>
const ll mod = 1e9 + 7;
int n, m, ans, a[100001];
int l, r, mid;
int x, ctrl;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    cin>>m;
    for(int i=1; i<=m; i++){
        cin>>ctrl>>x;
        if(!ctrl){
            l=1; ans=1; r=n+1;
            while(r-l>1){
                mid=(r+l)/2;
                if(a[mid]<=x){
                    l=mid;
                    ans=mid;
                }
                else r=mid;
            }
            if(a[l]!=x) cout<<-1<<'\n'; else cout<<l<<'\n';
        }
        else if(ctrl==1){
            l=1; r=n+1;
            while(r-l>1){
                mid=(r+l)/2;
                if(a[mid]<=x){
                    l=mid;

                }
                else r=mid;
            } cout<<l<<'\n';
        }
        else if(ctrl==2){
            l=0; r=n;
            while(r-l>1){
                mid=(r+l)/2;
                if(a[mid]>=x){
                    r=mid;
                }
                else l=mid;
            }
            cout<<r<<'\n';
        }
    }
}