/*
- De ce fetele alearga mai incet ca baietii?
- Fiindca frecarea dinre 2 placi este mai mare ca frecarea dintre 2 bile!
*/
#include<stdio.h>
using namespace std;
int v[100005];
int tip0(int dr, int wanted)
{
    int st=1,m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]<=wanted)
            st=m+1;
        else
            dr=m-1;
    }
    m=(st+dr)/2;
    if(v[m]>wanted) --m;
    if(v[m]==wanted) return m;
    return -1;
}
int tip1(int dr, int wanted)
{
   int st=1,m;
   while(st<dr)
   {
        m=(st+dr)/2;
        if(v[m]<=wanted)
            st=m+1;
        else
            dr=m;
   }
   m=(st+dr)/2;
   if(v[m]>wanted) --m;
   return m;
}
int tip2(int dr, int wanted)
{
    int st=1,m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(v[m]<wanted)
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;
    if(v[m]<wanted) ++m;
    return m;
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int n,i,m,x,tip;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d %d",&tip,&x);
        if(tip==0) printf("%d\n",tip0(n,x));
        if(tip==1) printf("%d\n",tip1(n,x));
        if(tip==2) printf("%d\n",tip2(n,x));
    }

    fclose(stdout);
    fclose(stdin);
    return 0;
}