#include <fstream>
using namespace std;
int i,n,p,u,m,x,M,tip,j,pm,poz;
int v[100002];
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main() {
  f>>n;
  for (i=1;i<=n;i++)
    f>>v[i];
  f>>M;
  for (i=1;i<=M;i++) {
    f>>tip>>x;
    if (tip==0) {
      p=1;
      u=n;
      pm=-1;
      while (p<=u) {
        m=p+(u-p)/2;
        if (x==v[m])
            if (m>pm)
             pm=m;
        if (x>v[m])
            p=m+1;
        else
         u=m-1;
      }
     g<<pm<<'\n';
    }
    if (tip==1) {
      p=1;
      u=n;
      while (p<=u) {
        m=p+(u-p)/2;
        if (v[m]<=x) {
             poz = m;
            p = m+1;
        }
        else
         u = m-1;
      }
      g<<poz<<'\n';
    }
    if (tip==2) {
      p=1;
      u=n;
      while (p<=u) {
        m=p+(u-p)/2;
        if (x<=v[m]) {
            poz = m;
            u=m-1;
        }
        else
         p=m+1;
      }
      g<<poz<<'\n';
    }
  }
  g.close();
  return 0;
}