#include <fstream>
#include <iostream>
using namespace std;
int t[100005];
int main()
{
    int st, dr, N, mid,nr,i,M,poz=-1,ques;
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>N;
    for(i=1;i<=N;i++)
    {
        fin>>t[i];
    }
    fin>>M;
    for(i=1;i<=M;i++)
    {
        fin>>ques;
        fin>>nr;
        st=1;
        dr=N;
        if(ques==0)
        {
            //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
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(t[mid]==nr)
                {
                    poz=mid;
                    st=mid+1;
                }
                else if(t[mid]<nr)
                {
                    st=mid+1;
                }
                else
                {
                    dr=mid-1;
                }
            }
            fout<<poz;
        }
        else if(ques==1)
        {
            //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
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(t[mid]<=nr)
                {
                    poz=mid;
                    st=mid+1;
                }
                else if(t[mid]>nr)
                {
                    dr=mid-1;
                }

            }
            fout<<poz;
        }
        else if(ques==2)
        {
            //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
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(t[mid]>=nr)
                {
                    poz=mid;
                    dr=mid-1;
                }
                else if(t[mid]<nr)
                {
                    st=mid+1;
                }

            }
            fout<<poz;
        }


    }

    return 0;
}