#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)
    {
         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 && v[mij+1]<=x)
            return caut_bin1(mij+1,dr,x);
        if(v[mij]<=x && v[mij+1]>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 && v[mij-1]>=x)
            return caut_bin2(st,mij-1,x);
        if(v[mij]>=x && v[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;
}