#include<math.h>
#include<fstream>
using namespace std;

int cb(int v[],int dim, int st, int dr, int x){
    int mid;
    if(st > dim){
        return -1;
    }
    if(st > dr){
        return dr;
    }
    mid = st + (dr - st)/2;
    if(v[mid] <= x){
        return cb(v, dim, mid + 1, dr, x);
    }
    else{
        return cb(v, dim, st, mid - 1, x);
    }

}
int cb2(int v[], int dim, int st, int dr, int x){
    if(cb(v, dim, st, dr, x) == -1){
        x--;
        return cb2(v, dim, st, dr, x);
    }
    else{
        return cb(v, dim, st, dr, x);
    }
}
int cb3(int v[],int dim, int st, int dr, int x){
    int mid;
    if(st > dim){
        return -1;
    }
    if(st > dr){
        return st;
    }
    mid = st + (dr - st)/2;
    if(v[mid] >= x){
        return cb(v, dim, st, mid - 1, x);
    }
    else{
        return cb(v, dim, mid + 1, dr, x);
    }

}
int cb4(int v[], int dim, int st, int dr, int x){
    if(cb(v, dim, st, dr, x) == -1){
        x++;
        return cb4(v, dim, st, dr, x);
    }
    else{
        return cb3(v, dim, st, dr, x);
    }
}
int main()
{
    ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");

    int v[25000];
    int n, m, i, j, x, tip;
    cin>>n;
    for(i = 1; i <= n; i++){
        cin>>v[i];
    }
    cin>>m;
    for(i = 1; i <= m; i++){
        cin>>tip>>x;
        if(tip == 0){
            cout<<cb(v, n, 1, n, x)<<" ";
            cout<<"\n";
        }
        else if(tip == 1){
            cout<<cb2(v, n, 1, n, x);
            cout<<"\n";
        }
        else if(tip == 2){
            cout<<cb4(v, n, 1, n, x);
        }
    }
    return 0;
}