#include <fstream>

using namespace std;

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

int v[100001],n;

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

int cautbin0(int x)
{
    int st=1,dr=n,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x)
            st=mij+1;
        else
            dr=mij-1;

    }
    if(v[dr]==x)
        return dr;
    return -1;
}
int cautbin2(int x)
{
    int st=1,dr=n,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>=x)
            dr=mij-1;
        else
            st=mij+1;
    }
    return st;
}
int main()
{
    ios_base::sync_with_stdio(false);
    int i,m,k,x;
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    while(m)
    {
        in>>k>>x;
        if(k==0)
            out<<cautbin0(x);
        if(k==1)
            out<<cautbin1(x);
        if(k==2)
           out<<cautbin2(x);
        out<<"\n";
        m--;
    }
    return 0;
}