#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int n,i,m,c,x,st,dr,mij,r,v[100005];

int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
      cin>>v[i];
    cin>>m;
    for(i=1;i<=m;i++)
    {
      cin>>c>>x;
      if(c==0)
      {

        st=1;
        dr=n;
        while(st<=dr)
        {
          mij=(st+dr)/2;
          if(v[mij]==x)
          {
            r=mij;
            st=mij+1;
          }
          else
            if(v[mij]>x)
              dr=mij-1;
            else
              st=mij+1;
        }

        cout<<r<<"\n";
      }
      else if(c==1)
      {
        st=1;
        dr=n;
        while(st>=dr)
        {
          mij=(st+dr)/2;
          if(v[mij]<=x)
          {
            r=mij;
            st=mij+1;
          }
          else
            dr=mij-1;
        }
        cout<<r<<"\n";
      }
      else
      {
        st=1;
        dr=n;
        while(st<=dr)
        {
          mij=(st+dr)/2;
          if(v[mij]>=x)
          {
            r=mij;
            dr=mij-1;
          }
          else
            st=mij+1;
        }
        cout<<r<<"\n";
      }
    }
    return 0;
}