#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int found(int i,int j,int a[],int x,int n)
{

    int m=i+(j-i)/2;
    if((a[m]==x && m==n-1) || (m+1<n && a[m+1]>x))
        return m;
    if(a[m]<=x)
        found(m+1,j,a,x,n);
    else found(i,m,a,x,n);
}
int found1(int i, int j, int a[], int x, int n)
{

    int m=i+(j-i)/2;
    if(a[m]<=x && (m==n-1 || (m+1<n && a[m+1]>x)))
       return m;
    if(a[m]<=x)
        found1(m+1,j,a,x,n);
      else found1(i,m,a,x,n);

}
int found2(int i, int j, int a[], int x, int n)
{

    int m=i+(j-i)/2;
    if(a[m]>=x && (m==0 || (m-1>=0 && a[m-1]<x)))
       return m;
    if(x>a[m])
         found2(m+1,j,a,x,n); ///jumatatea mare
      else found2(i,m,a,x,n); ///jumatatea mica

}
int main()
{
    int a[100000];
    int n;
    in>>n;
    for(int i=0;i<n;i++)in>>a[i];
    int nr;
    in>>nr;
    for(int i=0;i<nr;i++)
    {
        int opt,searched;
        in>>opt>>searched;
        switch(opt)
        {
        case 0:
            {
                out<<found(0,n-1,a,searched,n)+1<<"\n";
                break;
            }
        case 1:
            {
                out<<found1(0,n-1,a,searched,n)+1<<"\n";
                break;
            }
        case 2:
            {
                out<<found2(0,n-1,a,searched,n)+1<<"\n";
                break;
            }
        }
    }
    return 0;
}