#include <iostream>
#include <fstream>
using namespace std;
int t[100000];
int main()
{
    ///Cautare binara Info arena
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int i,k,j,N,M,c,st,dr,mid,num;
    bool found=true;
    fin>>N;
    for(i=1;i<=N;i++)
    {
        fin>>t[i];
    }
    fin>>M;
    for(i=1;i<=M;i++)
    {
        fin>>c;
        st=1;
        dr=N;
        fin>>num;
        if(c==0)
        {
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(t[mid]>num)
                    dr=mid-1;
                else
                    st=mid+1;
            }
            if(t[dr]!=num)
                fout<<-1;
            else
                fout<<dr;
        }
        else if(c==1)
        {
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(t[mid]<=num)
                {
                    st=mid+1;
                }
                else
                {
                    dr=mid-1;
                }
            }
            fout<<dr;
        }
        else if(c==2)
        {
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(t[mid]<num)
                {
                    st=mid+1;
                }
                else
                {
                    dr=mid-1;
                }
            }
            fout<<st;
        }
        fout<<'\n';
    }
    return 0;
}