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

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

int v[N];

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

int bSearch2(int st, int dr, int nr)
{
    int m;
    while(st<dr) {
        m=(st+dr)/2;
        if(v[m]<nr) st=m+1;
        else dr=m;
    }
    m=(st+dr)/2;
    if(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;
        if(y==0)
            g<<bSearch0(1,n,x)<<'\n';
        if(y==1)
            g<<bSearch1(1,n,x)<<'\n';
        if(y==2)
            g<<bSearch2(1,n,x)<<'\n';
    }
}