#include <bits/stdc++.h>

using namespace std;

int n , i , a[100005], m , x , y , d;

int hei0(int n , int a[] , int x)
{
    int s , d , m , poz ;
    s=1;
    d=n;
    while(s<=d){
        m=(s+d)/2;
        if(a[m]<=x){
            if(a[m]==x)poz=m;
            s=m+1;
        }
        else d=m-1;
    }
    return poz ;
}
int hei1(int n , int a[] , int x)
{
    int s , d , m , poz ;
    s=1;
    d=n;
    while(s<=d){
        m=(s+d)/2;
        if(a[m]<=x)poz=m,s=m+1;
        else d=m-1;
    }
    return poz;
}
int hei2(int n , int a[] , int x)
{
    int s , d , m ,poz ;
    s=1;
    d=n;
    while(s<=d){
        m=(s+d)/2;
        if(a[m]>=x)poz=x,d=m-1;
        else s=m+1;
    }
    return poz;
}
int main()
{
    cin >> n ;
    for(i=1;i<=n;i++)cin >> a[i];
    for(i=1;i<=m;i++){
        cin >> y >> x ;
        if(y==0)d=hei0(n,a,x);
        else if(y==1)d=hei1(n,a,x);
        else if(y==2)d=hei2(n,a,x);
        cout << d << '\n';
    }
}