#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,i,l,r,x,mid,a[100001],b,nr;
int cautbin0(int x)
{
    int l=1;
    int r;
    r=n;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(a[mid]<=x)
        l=mid+1;
        else r=mid-1;

    }

        if(a[r]==x) return r;
        else return -1;
}
int cautbin1(int x)
{
    int l=1;
    int r;
    r=n;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(a[mid]<=x)
        l=mid+1;
        else
        r=mid-1;
    }
    return r;
}
int cautbin2(int x)
{
    int l=1;
    int r; r=n;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(a[mid]>=x)
        r=mid-1;
        else l=mid+1;
    }
    return l;
}

int main()
{
    fin>>n;
    for(i=1; i<=n; i++) fin>>a[i];
    fin>>nr;
    for(i=1; i<=nr; i++)
    {


        fin>>x>>b;
        if(x==0) fout<<cautbin0(b)<<'\n';
        else if(x==1) fout<<cautbin1(b)<<'\n';
       else if (x==2) fout<<cautbin2(b)<<'\n';
    }
    return 0;
}