#include <stdio.h>
#include <algorithm>
FILE *fin, *fout;
int n, m, a, b;
unsigned *v;
int main()
{
    fin = fopen("cautbin.in", "r");
    fout = fopen("cautbin.out", "w");
    fscanf(fin, "%d", &n);
    v = new unsigned int[n];
    for(int i =0; i< n; i++) fscanf(fin, "%d", &v[i]);
    fscanf(fin, "%d", &m);
    for(int i  = 0; i< m; i++)
    {
            fscanf(fin, "%d%d", &a, &b);
            if(a == 0)
                 if(!std::binary_search(v, v+n, b)){fprintf(fout, "-1\n");continue;}
                 else
                 {
                     fprintf(fout, "%d\n", std::upper_bound(v, v+n, b)-v);
                     continue;
                 }
            if(a == 1)
            {
                 fprintf(fout, "%d\n", std::lower_bound(v, v+n, b+1)-v);
                 continue;
            }
            if(a == 2)
            {
                 fprintf(fout, "%d\n", std::upper_bound(v, v+n, b-1)-v+1);
                 continue;
            }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}