#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
#define int long long
const int mod=1e9+7;
const int inf=1e5;
using namespace std;
std::multiset<int>::iterator it;
std::multiset<int>::iterator it1;

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

int binsearch0(int y){
    int l=1;
    int r=n;
    while(r>=l){
        int mid=l+(r-l)/2;
        if(a[mid]==y && (a[mid+1]>y || mid+1==n+1)) return mid;
        if(a[mid]<=y){l=mid+1; continue;}
        if(a[mid]>y){r=mid-1; continue;}
    }
    return -1;

}
int binsearch1(int y){
    int l=1;
    int r=n;
    while(r>=l){
        int mid=l+(r-l)/2;
        if(a[mid]<=y && (a[mid+1]>y || mid==n+1)) return mid;
        if(a[mid]<=y){l=mid+1; continue; }
        if(a[mid]>y){r=mid-1; continue; }

    }

}

int binsearch2(int y){
    int l=1;
    int r=n;
    while(r>=l){
        int mid=l+(r-l)/2;
        if(a[mid]>=y && (a[mid-1]<y || mid==n+1)) return mid;
        if(a[mid]<y){l=mid+1; continue; }
        if(a[mid]>=y){r=mid-1; continue; }

    }

}


signed 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;
        if(t==0){fin >> x; if(ans[t][x]==0) ans[t][x]=binsearch0(x); fout<<ans[t][x]<<endl; continue; }
        if(t==1){fin >> x; if(ans[t][x]==0) ans[t][x]=binsearch1(x); fout<<ans[t][x]<<endl; continue; }
        if(t==2){fin >> x; if(ans[t][x]==0) ans[t][x]=binsearch2(x); fout<<ans[t][x]<<endl; continue; }
    }
    return 0;
}