#include <fstream>
#define NMAX 100002
using namespace std;
ifstream  fin("cautbin.in");
ofstream fout("cautbin.out");
int N,M,v[NMAX];

void citire()
{
    fin>>N;

    for(int i=1; i<=N; i++)
    {
        fin>>v[i];
    }

    fin>>M;
}

int query0(int x)
{
    int ans,p1,p2,pmijl;
    ans=-1;
    p1=1;
    p2=N;

    while(p1<=p2)
    {
        pmijl=(p1+p2)/2;

        if(v[pmijl]==x)
        {
            ans=pmijl;
            p1=pmijl+1;
        }
        else
        {
            if(v[pmijl]>x)
            {
                p2=pmijl-1;
            }
            else
            {
                p1=pmijl+1;
            }
        }
    }

    return ans;
}

int query1(int x)
{
    int ans,p1,p2,pmijl;
    ans=0;
    p1=1;
    p2=N;

    while(p1<=p2)
    {
        pmijl=(p1+p2)/2;

        if(v[pmijl]<=x)
        {
            ans=pmijl;
            p1=pmijl+1;
        }
        else
        {
            p2=pmijl-1;
        }
    }

    return ans;
}

int query2(int x)
{
    int ans,p1,p2,pmijl;
    ans=0;
    p1=1;
    p2=N;

    while(p1<=p2)
    {
        pmijl=(p1+p2)/2;

        if(v[pmijl]>=x)
        {
            ans=pmijl;
            p2=pmijl-1;
        }
        else
        {
            p1=pmijl+1;
        }
    }

    return ans;
}

int main()
{
    citire();

    for(int q=1; q<=M; q++)
    {
        int op,x;
        fin>>op>>x;

        if(op==0)
        {
            fout<< query0(x);
        }

        if(op==1)
        {
            fout<< query1(x);
        }

        if(op==2)
        {
            fout<< query2(x);
        }

        fout<< "\n";
    }

    return 0;
}