#include <bits/stdc++.h>
#define DM 100005
using namespace std;
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");

int N,M,V[DM];
int query(int tip,int x)
{
    if(tip==0)
    {
      int st=1,dr=N;
      while(st<=dr)
      {
          int mij=(st+dr)/2;
          if(V[mij]==x)
          {
              while(V[mij]==x)
                mij++;
              return mij-1;
          }
          if(V[mij]>x)
          {
              dr=mij-1;
          }
          else st=mij+1;
      }
     return -1;

    }
    if(tip==1)
    {
        int st=1,dr=N;
        int mij;
        while(st<=dr)
        {
          mij=(st+dr)/2;
          if(V[mij]>x)
            dr=mij-1;
          else st=mij+1;
        }
        if(V[(st+dr)/2]>x)
            return (st+dr)/2-1;
        return (st+dr)/2;



    }
    if(tip==2)
    {
        int st=1,dr=N;
        int mij;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(V[mij]>=x)
                dr=mij-1;
            else st=mij+1;

        }
        if(V[(st+dr)/2]<x)
            return (st+dr)/2+1;
        return (st+dr)/2;
    }



}
int main()
{
    fi>>N;
    for(int i=1;i<=N;i++)
        fi>>V[i];
    fi>>M;
    for(int i=1;i<=M;i++)
    {
        int a,b;
        fi>>a>>b;
        fo<<query(a,b)<<'\n';
    }
    return 0;
}