#include <iostream>
#include <deque>
#include <vector>
#include <cstring>
#include <bitset>
#include <algorithm>
#define INF 1000010
#define uint unsigned int
#define ll long long
#define step(x) (x&(-x))
using namespace std;

int A[100010], N, M, t, x, i, st, dr, mid, sol;


int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &N);
    for(i = 1; i <= N; i++)
    {
        scanf("%d", &A[i]);
    }
    scanf("%d", &M);
    while(M--)
    {
        scanf("%d%d", &t, &x);
        if(t == 0)
        {
            sol = -1;
            st = 1;
            dr = N;
            while(st <= dr)
            {
                mid = (st + dr) / 2;
                if(A[mid] == x)
                    sol = max(sol, mid);
                if(A[mid] <= x)
                    st = mid + 1;
                else
                    dr = mid - 1;
            }
            printf("%d\n", sol);
        }
        if(t == 1)
        {
            sol = -1;
            st = 1;
            dr = N;
            while(st <= dr)
            {
                mid = (st + dr) / 2;
                if(A[mid] <= x)
                    sol = max(sol, mid);
                if(A[mid] <= x)
                    st = mid + 1;
                else
                    dr = mid - 1;
            }
            printf("%d\n", sol);
        }
        if(t == 2)
        {
            sol = N;
            st = 1;
            dr = N;
            while(st <= dr)
            {
                mid = (st + dr) / 2;
                if(A[mid] >= x)
                    sol = min(sol, mid);
                if(A[mid] < x)
                    st = mid + 1;
                else
                    dr = mid - 1;
            }
            printf("%d\n", sol);
        }
    }
    return 0;
}