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

    int n,m,v[100002],op,x;

int op0(int x)
{
int lo=1;
int hi=n,mid;
while(lo<=hi)
{
               mid = lo + (hi-lo)/2;
               if (v[mid]>x) hi=mid-1;  
               else if (v[mid]<x) lo=mid+1;
               else return mid;
               }  
    return -1;
    }
    
int op1(int x)
{
int lo=1;
int hi=n,mid,last=0;
while(lo<=hi)
{
               mid = lo + (hi-lo)/2;
               if (v[mid]<=x) last=mid,lo=mid+1;
               else hi=mid-1; 
               }  
    return last;
    }


int op2(int x)
{
int lo=1;
int hi=n,mid,last=0;
while(lo<=hi)
{
               mid = lo + (hi-lo)/2;
               if (v[mid]>=x) last=mid,hi=mid-1;
               else lo=mid+1; 
               }  
    return last;
    }

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%i",&n);
    for(int i=1;i<=n;scanf("%i",&v[i++]));
    scanf("%i",&m);
    for(int i=1;i<=m;i++)
    {
            scanf("%i%i",&op,&x);
            switch (op)
            {
            case 0: printf("%i\n",op0(x));break;       
            case 1: printf("%i\n",op1(x));break;     
            case 2: printf("%i\n",op2(x));break;           
                   }
                             }
    return 0;
    }