#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
/**
0 x - cea mai mare pozitie pe care se afla un element cu valoarea x
 sau -1 daca aceasta valoare nu se gaseste in sir

1 x - cea mai mare pozitie pe care se afla un element cu valoarea
mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic
numar al sirului este mai mic sau egal decat x

2 x - cea mai mica pozitie pe care se afla un element cu valoarea
mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
*/
int main()
{
    int t,p,x,v[100000],n;
    fin>>n;
    for(int i=0;i<n;i++) fin>>v[i];
    fin>>t;
    for(int i=1;i<=t;i++)
    {
        fin>>p>>x;
        int st=0,dr=n-1,poz=-1,mij;
        if(p==0)
        {
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(v[mij]==x)
                    {
                        poz=mij;
                        st=mij+1;
                    }
                else if(v[mij]<x)
                    st=mij+1;
                    else dr=mij-1;

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



        fout<<poz++<<"\n";///cred ca pozitiile sunt de la 1,nu de la 0
    }
    return 0;
}