#include <stdio.h>
#define NMax 100001

using namespace std;

int arr[NMax];

int cautareBinara(int x, int arr[],int l, int r)
{
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (arr[mid] == x)
        {
            while (mid < r && arr[mid] == x)
                mid++;
            return mid;
        }
        else if (arr[mid] < x)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }

    return -1;
}

int cautareBinara1(int x, int arr[], int l, int r)
{
    int min = r;
    while (l < r)
    {
        int mid = l + (r - l) / 2;
        if (arr[mid] >= x)
        {
            if (mid < min)
            {
                min = mid;
            }
        }
        if (arr[mid] <= x)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    while (arr[min - 1] >= x)
        min--;
    if (arr[min] == x)
        return min + 1;
    return min;
}

int cautareBinara2(int x, int arr[], int l, int r)
{
    int min = r;
    while (l < r)
    {
        int mid = l + (r - l) / 2;
        if(arr[mid] >= x)
        {
            if (mid < min)
            {
                min = mid;
            }
        }
        if (arr[mid] <= x)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    while (arr[min - 1] >= x)
        min--;
    return min + 1;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &arr[i]);
    }

    int M;
    scanf("%d", &M);
    for (int i = 0; i < M; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x == 0)
        {
            printf("%d\n", cautareBinara(y, arr, 0, N));
        }
        else if (x == 1)
        {
            printf("%d\n", cautareBinara1(y, arr, 0, N));
        }
        else
        {
            printf("%d\n", cautareBinara2(y, arr, 0, N));
        }
    }
}