#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
#define inf1 -999999999
#define inf2 +999999999
int i,m,n,v[100003];
int Binary_search(int q, int x)
{
    int sol=-1,l=0,r=n+1,mij;
    while( l<=r )
    {
        mij=l+(r-l)/2;
        if(v[mij] < x)
        {
           if( q == 2 )
              sol = mij;
            l=mij+1;

        }
        else if(v[mij] > x)
             {
                if( q == 1 )
                   sol = mij;
                r=mij-1;
             }
             else if( q == 0 )
                  {
                     sol = mij;
                     l = mij+1;
                  }
                  else if( q == 2 )
                          r = mij-1;
                       else
                          l = mij+1;
    }
    if( q == 2 && v[sol+1] <= x ) sol++;
    if( q == 1 && v[sol-1] >= x ) sol--;
    return sol;
}
int main()
{
    int x,q;
    f>>n; for(i=1;i<=n;++i) f>>v[i];
    v[0] = inf1;
    v[n+1] = inf2;
    f>>m; for(i=1;i<=m;++i){f>>q>>x; g<<Binary_search(q,x)<<'\n';}
    f.close(); g.close();
    return 0;
}