#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[100005],n;
    fin>>n;
    for(int i=1; i<=n; i++) fin>>v[i];
    fin>>t;
    for(int i=1; i<=t; i++)
    {
        fin>>p>>x;
        int st=1,dr=n,mij,poz=-1;
        if(p==0)
        {
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(v[mij]<=x)
                {
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            mij=(st+dr)/2;
            if(v[mij]>x) mij--;
            if(v[mij]==x) poz=mij;

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



        fout<<poz<<"\n";
    }
    return 0;
}