#include <stdio.h>
#include <stdlib.h>
#define dim 100001

int n, a[dim];

int binary_search(int val)
{
    int i, step;
    for(step = 1 ; step < n ; step <<=1 );

    for(i = 1 ; step ; step >>= 1)
    {
        if(i + step < n && a[i + step] < val){
            i += step;
        }
    }

    return i;

}
int main()
{

FILE *fin, *fout;
fin = fopen("cautbin.in", "r");
fout = fopen("cautbin.out", "w");
    int m, i, mod, x, rez;
    fscanf(fin, "%d", &n);

    for(i = 1 ; i <= n ; i++)
    {
        fscanf(fin, "%d", &a[i]);
    }

    fscanf(fin, "%d", &m);
    for(i = 1 ; i <= m ; i++)
    {
        fscanf(fin, "%d %d", &mod, &x);
        rez = binary_search(x);

        switch(mod){
            case 0:
                while(rez <= n && a[rez] <= x) ++rez;
                if(rez <= n) fprintf(fout, "-1\n");
                else fprintf(fout, "%d\n", rez-1 );
                break;
            case 1:
                while(rez <= n && a[rez] <= x) ++rez;
                fprintf(fout, "%d\n", rez-1);
                break;
            case 2:
                while(rez <= n && a[rez] < x) ++rez;
                fprintf(fout, "%d\n", rez);
                break;

        }
    }
    return 0;
}