#include <iostream>
#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int v[100001];

int bsearch0 (int p, int u, int x) {
    int m;
    while(p<=u) {
        m=(p+u)/2;
        if (v[m]<=x)
            p=m+1;
        else
            u=m-1;
    }
    m=(p+u)/2;

    if(v[m]>x) m--;
    if (v[m]==x)
        return m;
    return -1;
}

int bsearch1 (int p, int u, int x) {
    int m,n=u;
    while(p<u){
        m=(p+u)/2;
        if(v[m]<=x)
            p=m+1;
        else
            u=m;
    }

    m=(p+u)/2;
    if(v[m]>x)
       m--;
    return m;
}

int bsearch2 (int p, int u, int x) {
    int m;
    while(p<u) {
        m=(p+u)/2;
        if(v[m]<x)
            p=m+1;
        else
            u=m;
    }

    m=(p+u)/2;
    if(v[m]<x)
       m++;
    return m;
}

int main()
{
    int n,i,m,x,d;
    f>>n;
    for(i=1; i<=n; i++)
        f>>v[i];

    f>>m;
    for(i=1; i<=m; i++){
       f>>d>>x;
       if(d==0) g<<bsearch0(1, n, x)<<"\n";
       else
        if(d==1) g<<bsearch1(1, n, x)<<"\n";
       else
        g<<bsearch2(1, n, x)<<"\n";
    }


    return 0;
}