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

const int NMAX=100010;
int v[NMAX];

int bs0(int st, int dr, int val){
    int mij;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]<=val)
            st=mij+1;
        else
            dr=mij-1;
    }
    mij=(st+dr)/2;
    if(v[mij]>val)
        mij--;
    if(v[mij]==val)
        return mij;
    return -1;
}

int bs1(int st, int dr, int val){
    int mij;
    while(st<dr){
        mij=(st+dr)/2;
        if(v[mij]<=val)
            st=mij+1;
        else
            dr=mij;
    }
    mij=(st+dr)/2;
    if(v[mij]>val)
        mij--;
    return mij;
}

int bs2(int st, int dr, int val){
    int mij;
    while(st<dr){
        mij=(st+dr)/2;
        if(v[mij]<val)
            st=mij+1;
        else
            dr=mij;
    }
    mij=(st+dr)/2;
    if(v[mij]<val)
        mij++;
    return mij;
}

int main(){
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int n,m;
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%d", &v[i]);
    scanf("%d", &m);
    while(m--){
        int tip,val;
        scanf("%d%d", &tip, &val);
        if(tip==0)
            printf("%d\n", bs0(1, n, val));
        if(tip==1)
            printf("%d\n", bs1(1, n, val));
        if(tip==2)
            printf("%d\n", bs2(1, n, val));
    }
    return 0;
}