#include <iostream>
#include <fstream>
using namespace std;

int cautare_binara1(int v[], int nr, int n){
    int dr=n-1, st=0, mij;
    while (st<dr){
        mij=(dr+st)/2;

        if (v[mij]<=nr)
            st=mij+1;

        else dr=mij-1;

    }
    //cout<<st;
    if (v[st]!=nr && v[st-1]!=nr)
        return -1;
    if (v[st-1]==nr)
        --st;
    while (v[st]==nr && st <n)
        ++st;
    return st;
}

int cautare_binara2(int v[], int nr, int n){
    int dr=n-1,st=0,mij;
    while (st<dr){
        mij=(dr+st)/2;

        if (v[mij]<=nr)
            st=mij+1;

        else dr=mij-1;
    }
    //cout<<st;
    if (v[st]>nr && v[st-1]>nr)
        return -1;
    if (v[st-1]<=nr)
        --st;
    while (v[st]<=nr && st<n)
        ++st;
    return st;
}

int cautare_binara3(int v[], int nr, int n){
    int dr=n-1,st=0,mij;
    while (st<dr){
        mij=(dr+st)/2;

        if (v[mij]<nr)
            st=mij+1;

        else dr=mij-1;
    }
    //cout<<st;
    if (v[st]<nr)
        return -1;
    bool ok=0;
    while (v[st]>=nr && st){
        --st;
        ok=1;
    }
    return st+1+ok;
}

int main(){
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int n;
    fin>>n;
    int v[n];
    for (int i=0; i<n; ++i)
        fin>>v[i];
    int m;
    fin>>m;
    short int tip;
    int nr;
    fin>>tip>>nr;
        switch (tip){
            case 0: fout<<cautare_binara1(v,nr,n);
                break;
            case 1: fout<<cautare_binara2(v,nr,n);
                break;
            case 2: fout<<cautare_binara3(v,nr,n);
                break;
        }
    for (int i=1; i<m; ++i){
        fin>>tip>>nr;
        switch (tip){
            case 0: fout<<'\n'<<cautare_binara1(v,nr,n);
                break;
            case 1: fout<<'\n'<<cautare_binara2(v,nr,n);
                break;
            case 2: fout<<'\n'<<cautare_binara3(v,nr,n);
                break;
        }
    }
}