#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 == 1 ) sol = mij;
           l=mij+1;  }
        else if(v[mij] > x)
        {  if( q == 2 ) sol = mij;
           r=mij-1;
        }else{ sol = mij;
               if( q == 2 ) r = mij-1;
               else l = mij+1;  } }
    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;
}