#include <fstream>
using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int n,a[100];

int cautbin(int key){
    int st = 1, dr = n,mij;
    while(st <= dr){
        mij = (st+dr)/2;
        if(key < a[mij]) dr = mij-1;
        else st = mij+1;
    }
    mij = (st+dr)/2;
    if(a[mij] > key) mij--;
    if(a[mij] == key) return mij;
    return -1;
}
int cautbin1(int key){
    int st = 1, dr = n,mij;
    while(st < dr){
        mij = (st+dr)/2;
        if(a[mij] <= key) st = mij+1;
        else dr = mij;
    }
    mij = (st+dr)/2;
    if(a[mij] > key) mij--;
    return mij;
}

int cautbin2(int key){
    int st = 1, dr = n,mij;
    while(st < dr){
        mij = (st+dr)/2;
        if(a[mij] >= key) dr = mij;
        else st = mij+1;
    }
    mij = (st+dr)/2;
    if(a[mij] < key) mij++;
    return mij;
}

int main()
{
    int i;
    cin>>n;
    for(i = 1; i <= n; i++){
        cin>>a[i];
    }
    int x,m,p;
    cin>>m;
    for(i = 0; i < m; i++){
        cin>>p>>x;
        if(p == 0)
            cout<<cautbin(x)<<"\n";
        else if(p == 1)
            cout<<cautbin1(x)<<"\n";
        else cout<<cautbin2(x)<<"\n";
    }
}