#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int step,i,j,m,n,v[100003];
int Binary_search(int q, int x)
{
    for(step = 1 ; step <= n ; step <<= 1);
    for( j = 0 ; step ; step >>= 1)
        if(q == 0) { if( j+step <= n && v[j+step] <= x ) j += step; }
        else if(q == 1) { if( j+step <= n && v[j+step] <= x ) j += step; }
             else { if( j+step <= n && v[j+step] <= x && v[j+step-1] < x ) j += step; }

    if(q == 0) return j = ( v[j] == x ) ? j :-1;
    else if(q == 1) return j;
         else return j = ( v[j] >= x ) ? j : j+1;
}
int main()
{
    int x,q;
    f>>n; for(i=1;i<=n;++i) f>>v[i];
    f>>m; for(i=1;i<=m;++i){f>>q>>x; g<<Binary_search(q,x)<<'\n';}
    f.close(); g.close();
    return 0;
}