#include <cstdio>

using namespace std;
int n,v[100005],i,m,tip,x;

int cautare0(int x)
{
    int s=1,d=n,mij;
    while(s<=d)
    { mij=(s+d)/2;
      if(x==v[mij]&& x<v[mij+1] || v[mij]==x && mij==n) return mij;
      else if(x>=v[mij]) s=mij+1;
          else if(x<v[mij]) d=mij-1;

    }
    return -1;
}

int cautare1(int x)
{
    int s=1,d=n,mij;
    while(s<=d)
    { mij=(s+d)/2;
      if((v[mij]<=x&&v[mij+1]>x)||(v[mij]<=x&&mij==n)) return mij;
        else if(v[mij]<x) s=mij+1;
        else if(v[mij]==x) s=mij+1;
        else if(v[mij]>x) d=mij-1;
    }
}


int cautare2(int x)
{ int s=1,d=n,mij;
  while(s<=d)
    { mij=(s+d)/2;
      if(v[mij]>=x&&v[mij-1]<x) return mij;
        else if(v[mij]<x) s=mij+1;
        else if(v[mij]==x) d=mij-1;
        else if(v[mij]>x) d=mij-1;
    }
}
int main()
{
    freopen ("cautbin.in","r",stdin);
    freopen ("cautbin.out","w",stdout);
    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",cautare0(x));
        if(tip==1) printf("%d\n",cautare1(x));
        if(tip==2) printf("%d\n",cautare2(x));
    }
    return 0;
}