#include<fstream>
using namespace std;

const int NMAX = 100010;
int N,M,x,op,i,A[NMAX];

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int C0(int l, int r, int x);
int C1(int l, int r, int x);
int C2(int l, int r, int x);

int main()
{
    cin>>N;
    for (i=1;i<=N;i++) cin>>A[i];
    cin>>M;
    while (M--)
    {
        cin>>op>>x;
        if (op==0) cout<<C0(1,N,x);
        if (op==1) cout<<C1(1,N,x);
        if (op==2) cout<<C2(1,N,x);
        cout<<"\n";
    }

    return 0;
}

int C0(int l, int r, int x)
{
    if (l==r) return (A[l]==x) ? l : -1;
    int mij=(l+r)/2;
    if (A[mij+1]>x) return C0(l,mij,x);
    return C0(mij+1,r,x);
}
int C1(int l, int r,int x)
{
    if (l==r) return l;
    int mij=(l+r)/2;
    if (A[mij+1]>x) return C1(l,mij,x);
    return C1(mij+1,r,x);
}
int C2(int l, int r, int x)
{
    if (l==r) return l;
    int mij=(l+r)/2;
    if (A[mij]>=x) return C2(l,mij,x);
    return C2(mij+1,r,x);
}