#include <fstream>

using namespace std;

int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

    unsigned long long int n;
    fin>>n;

    unsigned long long int v[100001];

    unsigned long long int i;
    for(i=0;i<n;i++)
    {
        fin>>v[i];
    }

    unsigned long long int m;
    fin>>m;

    unsigned long long int tip,numar;

    unsigned long long int cap=0;
    unsigned long long int coada=n-1;
    unsigned long long int mijl;
     long long int raspuns;

    for(i=0;i<m;i++)
    {
        fin>>tip;
        fin>>numar;

        if(tip==0)
        {
           cap=0;
           coada=n-1;
           mijl=(n-1)/2;
           raspuns=-1;

           while(cap<=coada)
           {
              if(v[mijl]==numar)
              {
                  raspuns=mijl;
                  cap=mijl+1;
              }
              else if(v[mijl]<numar)
              {
                  cap=mijl+1;
              }
              else
              {
                  coada=mijl-1;
              }

              mijl=(cap+coada)/2;
           }
           fout<<raspuns+1<<'\n';
        }
        else if(tip==1)
        {

           cap=0;
           coada=n-1;
           mijl=(n-1)/2;
           raspuns=-1;

           while(cap<=coada)
           {
              if(v[mijl]<=numar)
              {
                  raspuns=mijl;
                  cap=mijl+1;
              }
              else
              {
                  coada=mijl-1;
              }

              mijl=(cap+coada)/2;
           }
           fout<<raspuns+1<<'\n';
        }
        else
        {
           cap=0;
           coada=n-1;
           mijl=(n-1)/2;
           raspuns=-1;

           while(cap<=coada)
           {
              if(v[mijl]>=numar)
              {
                  raspuns=mijl;
                  coada=mijl-1;
              }
              else
              {
                  cap=mijl+1;
              }

              mijl=(cap+coada)/2;
           }

           fout<<raspuns+1<<'\n';
        }
    }

    fin.close();
    fout.close();
    return 0;
}