#include <iostream>
#include<fstream>
#include<string>

#define N 100001
using namespace std;

int n,option,key,m;
int a[N];

int midpoint(int st,int dr)
{
    return ((st+dr)/2);
}

int BinarySearch0(int st,int dr,int key)
{
    int mid=0;
    int poz=-1;
    while(st<=dr)
    {
        mid=midpoint(st,dr);
        if(a[mid]>key)
            dr=mid-1;
        else if(a[mid]<=key)
            {
                poz=mid;
                st=mid+1;
            }
    }
    return poz;
}

int BinarySearch1(int st,int dr,int key)
{
    int mid=0;
    int poz=1;
    while(st<=dr)
    {
        mid=midpoint(st,dr);
        if(a[mid]>key)
            dr=mid-1;
        else if(a[mid]<=key)
            {
                poz=mid;
                st=mid+1;
            }
    }
    return poz;
}

int BinarySearch2(int st,int dr,int key)
{
    int mid=0;
    int poz=dr;
    while(st<=dr)
    {
        mid=midpoint(st,dr);
        if(a[mid]>=key)
        {
            poz=mid;
            dr=mid-1;
        }
        else if(a[mid]<key)
            {
                st=mid+1;
            }
    }
    return poz;
}

int main()
{
    freopen ("cautbin.in","r",stdin);
    freopen ("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&option);
        scanf("%d",&key);
        if(option==0)
            printf("%d\n",BinarySearch0(1,n,key));
        else if(option==1)
           printf("%d\n",BinarySearch1(1,n,key));
        else if(option==2)
            printf("%d\n",BinarySearch2(1,n,key));
    }
    return 0;
}