#include <bits/stdc++.h>

using namespace std;

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

long long a[100005],n,k,nr1,nr2;

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

int CautareBinara1(long x){
    int st=1, dr=n, poz=0;
    while (st<=dr){
        int mij=(st+dr)/2;
        if (a[mij]<=x){poz=mij;
                       st=mij+1;}
        else dr=mij-1;
    }
    return poz;
}

int CautareBinara2(long x){
    int st=1, dr=n, poz=0;
    while (st<=dr){
        int mij=(st+dr)/2;
        if (a[mij]>=x){poz=mij;
                       dr=mij-1;}
        else st=mij+1;
    }
    return poz;
}

int main()
{
    f>>n;
    for (int i=1;i<=n;i++)
        f>>a[i];
    f>>k;
    while (k){
        f>>nr1>>nr2;
        if (nr1==0) g<<CautareBinara0(nr2)<<'\n';
        else if (nr1==1) g<<CautareBinara1(nr2)<<'\n';
             else g<<CautareBinara2(nr2)<<'\n';
        k--;
    }
    return 0;
}