#include <fstream>
#include <iostream>

using namespace std;

#define N 100001
int V[N];


fstream f("cautbin.in",ios::in);
fstream g("cautbin.out",ios::out);

int CBCif0(int x,int n);
int CBCif1(int x, int n);
int CBCif2(int x, int n);

int main()
{
    int x,n,M,Cif;
    f>>n;
    for(int i=1;i<=n;i++)
        f>>V[i];
    f>>M;
    for(int i=0;i<M;i++)
    {
        f>>Cif;
        f>>x;
        if(Cif==0)
        {
            g<<CBCif0(x,n)<<"\n";
        }
        if(Cif==1)
        {
            g<<CBCif1(x,n)<<"\n";
        }
        if(Cif==2)
        {
            g<<CBCif2(x,n);
        }
    }

    return 0;
}

int CBCif0(int x,int n)
{
    int mij,ind=1;
    while(ind<n)
    {
        mij=(ind+n)/2;
        if(V[mij]<=x)
            ind=mij+1;
        else
            ind=mij-1;
    }
    mij=(ind+n)/2;
    while(V[mij]>x)
        mij--;
    if(V[mij]==x)
        return mij;

    return -1;
}

int CBCif1(int x, int n)
{
    int mij,ind=1;
    while(ind<n)
    {
        mij=(ind+n)/2;
        if(V[mij]<=x)
            ind=mij+1;
        else
            ind=mij-1;
    }
    mij=(ind+n)/2;
    while(V[mij]>x)
        mij--;
    return mij;
}

int CBCif2(int x, int n)
{
    int mij, ind=1;
    while(ind<n)
    {
        mij=(ind+n)/2;
        if(V[mij]<=x)
            ind=mij+1;
        else
            ind=mij-1;
    }
    mij=(ind+n)/2;
    while(V[mij]>=x)
        mij--;

    return mij+1;
}