#include <bits/stdc++.h>

using namespace std ;

int n , i , a[100005] , st , dr, poz , m , x , c , k , M ;

ifstream f("cautbin.in") ;
ofstream g("cautbin.out") ;

int cer0(int n , int c , int x , int a[])
{
    int st=1 , dr=n ,poz=0 , m ;
        while(st<=dr)
    {
        m=(st+dr)/2 ;
        if(a[m]>x) dr=m-1 ;
        if(a[m]<x) st=m+1 ;
        if(a[m]==x) st=m+1 , poz=m ;
    }
    return poz ;
}

int cer1(int n , int c , int x , int a[])
{
    int st=1 , dr=n ,poz=0 , m ;
        while(st<=dr)
    {
        m=(st+dr)/2 ;
        if(a[m]>x) dr=m-1 ;
        if(a[m]<=x) st=m+1 , poz=m;
    }
    return poz ;
}

int cer2(int n , int c , int x , int a[])
{
    int st=1 , dr=n ,poz=0 , m ;
        while(st<=dr)
    {
        m=(st+dr)/2 ;
        if(a[m]>=x) dr=m-1 , poz=m ;
        if(a[m]<x) st=m+1 ;
    }
    return poz ;
}

int main()
{
    f >> n ;
    for(i=1;i<=n;i++) f >> a[i] ;
    f >> M ;
    for(i=1;i<=M;i++)
    {
        f >> c >> x ;
        if(c==0) k=cer0(n , c , x , a) ;
        if(c==1) k=cer1(n , c , x , a) ;
        if(c==2) k=cer2(n , c , x , a) ;
        g << k << '\n' ;
    }
}