#include <bits/stdc++.h>
#define in "cautbin.in"
#define out "cautbin.out"
#define M 100005
using namespace std;

ifstream fin(in);
ofstream fout(out);

int a[M];

int n,i,m,rs,q,x;

int bin0(int n,int x)
{
    int st,dr,m;
    st=1;
    dr=n;
    while (st<=dr){
        m=(st+dr)/2;
        if (x>=a[m]) st=m+1;
        else dr=m-1;
    }
    if (a[st]==x) return st;
    if (a[dr]==x) return dr;
    return -1;
}

int bin1(int n,int x){
    int st,dr,m;
    st=1;
    dr=n;
    while (st<=dr){
        m=(st+dr)/2;
        if (x>=a[m]) st=m+1;
        else dr=m-1;
    }
    if (a[dr]>x) dr--;
    return dr;
}

int bin2(int n,int x){
    int st,dr,m;
    st=1;
    dr=n;
    while (st<=dr){
        m=(st+dr)/2;
        if (x<=a[m]) dr=m-1;
        else st=m+1;
    }
    if (a[dr]<x) dr++;
    if (a[dr]<x) dr++;
    return dr;
}

int main()
{
    fin>>n;
    for(i=1;i<=n;i++) fin >> a[i];
    fin>>m;
    for (i=1;i<=m;i++){
        fin >>q>>x;
        if (q==0) rs=bin0(n,x);
        if (q==1) rs=bin1(n,x);
        if (q==2) rs=bin2(n,x);
        fout <<rs<<endl;
    }

    return 0;
}