#include<stdio.h>
#include<stdlib.h>

using namespace std;

int v[100001],a,st,dr,mj,b; 

int b1(int a, int st, int dr)
{
    int val = -1;
    while (st<=dr)
    {
          mj=(st+dr)/2;
          if (a == v[mj]) val = mj;
          if (a>=v[mj]) st=mj+1;
          else dr=mj-1;    
             }
     return val; 
}


int b2(int a, int st, int dr)
{
    b = 0;
    while (st<=dr)
    {
          mj=(st+dr)/2;
          if (a>=v[mj]) {b=mj; st=mj+1;}
     else dr=mj-1;       
             }
     return b;
     }
int b3(int a, int st, int dr)
{
    b = 0;
    while (st<=dr)
    {
          mj=(st+dr)/2;
          if (a<=v[mj]) {b=mj; dr=mj-1;}
          else st=mj+1;
          }
    return b;
}
 
          
          
int main()
{int n,i,m,t;
    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",&t,&a);
    
    if (t==0)
    printf("%d\n",b1(a, 1, n));
    else if (t==1)
    printf("%d\n",b2(a, 1, n));
    else
    printf("%d\n",b3(a, 1, n));
}
    
return 0;
}