#include <iostream>
#include<cstdio>

using namespace std;
int v[100001],n,m,tip,valoare;

int f0(int stg, int drp, int valoare)
{


   if(stg == drp){ if(v[stg]==valoare)return stg; else return -1; }
    else{

        int mij=((stg+drp)>>1)+1;

        if(v[mij]<=valoare)return f0(mij,drp,valoare);

        else return f0(stg,mij-1,valoare);



    }

}
int f1(int stg,int drp,int valoare)
{


   if(stg == drp){ return stg;  }
    else{

        int mij=(stg+drp+1)>>1;

        if(v[mij]>valoare)return f1(stg,mij-1,valoare);

        else return f1(mij,drp,valoare);



    }
}

int f2(int stg,int drp, int valoare)
{


   if(stg == drp){ return stg;  }
    else{

        int mij=(stg+drp)>>1;

        if(v[mij]>=valoare)return f2(stg,mij,valoare);

        else return f2(mij+1,drp,valoare);



    }
}


int main()
{
 freopen("cautbin.in","r",stdin);
 freopen("cautbin.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++)scanf("%d",&v[i]);
scanf("%d",&m);
for(int i=1; i<=m; i++)
{
    scanf("%d %d",&tip,&valoare);
    if(tip==0)printf("%d\n",f0(1,n,valoare));
    if(tip==1)printf("%d\n",f1(1,n,valoare));
    if(tip==2)printf("%d\n",f2(1,n,valoare));
}


    return 0;
}