#include <bits/stdc++.h>
#define N 100001
using namespace std;

/// cautbin
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, a[N], m, x, y;

int main(){
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>a[i];
    }
    fin>>m;
    while(m--){
        fin>>y>>x;
        if(y==0){
            int ub = upper_bound(a+1, a+n, x)-a-1;
            if(a[ub]==x && ub>=1 && ub<=n){
                fout<<ub;
            }else{
                fout<<-1;
            }
        }else if(y==1){
            int lb = lower_bound(a+1, a+n, x+1)-a-1;
            fout<<lb;
        }else{
            int ub = upper_bound(a+1, a+n, x-1)-a;
            fout<<ub;
        }
        fout<<endl;
    }
    return 0;
}