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

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

int v[N];

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

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

int bSearch2(int st, int dr, int nr)
{
    int m=(st+dr)/2;
    while(st<=dr) {
        if(v[m]<=nr) dr=m-1;
        else st=m+1;
        m=(st+dr)/2;
    }
    while(v[m]<nr) m++;
    return m;
}

int n,m,x,y;
int main() {
    f>>n;
    for(int i=1;i<=n;i++)f>>v[i];
    f>>m;
    for(int i=1;i<=m;i++) {
        f>>y>>x;
        switch(y) {
            case 0: { g<<bSearch0(1,n,x)<<'\n'; break; }
            case 1: { g<<bSearch1(1,n,x)<<'\n'; break; }
            case 2: { g<<bSearch2(1,n,x)<<'\n'; break; }
            default: break;
        }
    }

}