#include<stdio.h>

int n,v[100001];

int cb0(int x,int st,int dr)
{
    if(st > dr) return -1;
    int mijl = st + (dr-st)/2;
    if(v[mijl] == x) { while(v[++mijl] == x); return mijl; }
    else if(v[mijl] < x) return cb0(x,mijl+1,dr);
    else return cb0(x,st,mijl-1);
}

int cb1(int x)
{
    int st,dr,mijl,last = 0;
    for(st = 0,dr = n-1; st <= dr; )
    {
         mijl = st+(dr-st)/2;
         if(v[mijl] <= x) st = mijl+1,last = mijl; 
         else dr = mijl-1; 
    }
    return last+1;
}

int cb2(int x)
{
    int st,dr,mijl,last = n+1;
    for(st = 0,dr = n-1; st <= dr; )
    {
         mijl = st+(dr-st)/2;
         if(x <= v[mijl]) dr = mijl-1,last = mijl; 
         else st = mijl+1; 
    }
    return last+1;
}

int main()
{
    int va,i,x,m;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    
    
    scanf("%d",&n);
    for(i = 0; i < n; ++i)
      scanf("%d",&v[i]);
      
    scanf("%d",&m);  
    
    for(; m ; m--)
    {
        scanf("%d %d",&va,&x);
        if(!va)
           printf("%d\n",cb0(x,0,n-1));  
        else if(va == 1)
           printf("%d\n",cb1(x));
        else
           printf("%d\n",cb2(x));
    }
    fclose(stdin); fclose(stdout);
    return 0;
}