#include <fstream>
#define nmax 100002
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[nmax],n,m;
int caut_bin0( int st, int dr,  int x)
{
    if(st>dr) return -1;
    if(st==dr && v[st]==x) return st;
    if(st==dr) return -1;
    if(st<dr)
    {
        int mij=st+(dr-st)/2;
        if(v[mij]<x || (v[mij]==x && v[mij+1]==x))
            return caut_bin0(mij+1,dr,x);
        if(v[mij]>x)
            return caut_bin0(st,mij-1,x);
        if(v[mij]==x && v[mij+1]>x)
            return mij;
    }
}
int caut_bin1( int st, int dr,  int x)
{
    if(st<=dr)
    {
        int mij=st+(dr-st)/2;
        if(v[mij]>x)
            return caut_bin1(st, mij-1,x);
        if(v[mij]<=x)
        {
            if(mij==n) return mij;
            if(v[mij+1]<=x)
                return caut_bin1(mij+1,dr,x);
            return mij;
        }
    }
}
int caut_bin2( int st, int dr, int x)
{
    if(st<=dr)
    {
        int mij=st+(dr-st)/2;
        if(v[mij]<x)
            return caut_bin2(mij+1,dr,x);
        if(v[mij]>=x)
        {
            if(mij==1) return mij;
            if(v[mij-1]>=x)
                return caut_bin2(st,mij-1,x);
            return mij;
        }
    }
}
int main()
{
    f>>n;
    for( int i=1; i<=n; ++i)
        f>>v[i];
    f>>m;
    for( int i=1; i<=m; ++i)
    {
        int tip_cautare,x;
        f>>tip_cautare>>x;
        if(tip_cautare==0)
            g<<caut_bin0(1,n,x)<<'\n';
        else if(tip_cautare==1)
            g<<caut_bin1(1,n,x)<<'\n';
        else g<<caut_bin2(1,n,x)<<'\n';
    }
    return 0;
}