#include <stdio.h>
#include <stdlib.h>
#define MAX 100002

int n, m;
int v[MAX];
int c0(int x)
{
    int st = 1;
    int dr = n;
    while(st < dr)
    {
        int mid = (st + dr) / 2;
        if( v[mid] <= x)
            st = mid + 1;
        else
            dr = mid -1;
    }
    if (v[st] == x)
        return st;
    if(v[st - 1] == x)
        return st - 1;
    return -1;
}

int c1(int x)
{
    int st = 1;
    int dr = n;
    while(st < dr)
    {
        int mid = (st + dr) / 2;
        if ( v[mid] > x)
            dr = mid -1;
        else
            st = mid + 1;
    }
    if(v[dr] != x && v[dr + 1] == x)
        return dr + 1;
    if(v[dr] > x)
        --dr;
    return dr;
}

int c2(int x)
{
    int st = 1;
    int dr = n;
    while(st < dr)
    {
        int mid = (st + dr) / 2;
        if(v[mid] <= x)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    if((v[dr] != x && v[dr - 1] == x) || ( v[dr] == x && v[dr - 1] == x))
        return dr - 1;
    if(v[dr] < x)
        ++dr;
    return dr;
}

FILE* fin;
FILE* fout;
int main()
{
    fin = fopen("cautbin.in", "r");
    fout = fopen("cautbin.out", "w");
    fscanf(fin, "%d", &n);
    int i;
    for(i = 1; i <= n; i++)
        fscanf(fin, "%d", &v[i]);
    fscanf(fin, "%d", &m);
    for(i = 0; i < m ; i++)
    {
        int tip, x;
        fscanf(fin, "%d", &tip);
        fscanf(fin, "%d", &x);
        if(tip == 0)
            fprintf(fout, "%d\n", c0(x));
        if(tip == 1)
            fprintf(fout, "%d\n", c1(x));
        if(tip == 2)
            fprintf(fout, "%d\n", c2(x));
    }

    return 0;
}