#include <iostream>
#include <fstream>

using namespace std;

int v[100010],N,M;

int CB0(int st, int dr, int x)

{
    int mij;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (v[mij] == x && (mij + 1 <= N && v[mij + 1] != x)) {
            return mij;
        }
        else if ((v[mij] == x && v[mij + 1] == x) || v[mij] < x) {
            st = mij + 1;
        }
        else if (v[mij] > x) {
            dr = mij - 1;
        }

    }
    return -1;
}

int CB1(int st, int dr, int x)
{

    int mij;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (v[mij] <= x) {
            if (mij + 1 <= N && v[mij + 1] <= x)
                st = mij + 1;
            else
                return mij;
        }
        else {
            dr = mij - 1;
        }
    }

    return -1;
}

int CB2(int st,int dr,int x)
{

    int mij;
    /*if(st<=dr)
    {
        mij=st+(dr-st)/2;
        if(x<=v[mij])
            if(x<=v[mij-1] && mij!=1) return CB2(st,mij-1,x);
                else
                    return mij;
        else
            return CB2(mij+1,dr,x);
    }*/
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (v[mij] >= x) {
            if (mij - 1 >= 1 && v[mij - 1] >= x) {
                dr = mij - 1;
            }
            else
                return mij;
        }
        else
            st = mij + 1;
    }
    return -1;
}

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int op,val;
    f>>N;
    for (int i=1;i<=N;i++) f>>v[i];
    f>>M;
    for(int i=0;i<M;i++)
        {f>>op>>val;
        if(op==0) g<<CB0(1,N,val)<<'\n';
        else
            if(op==1)g<<CB1(1,N,val)<<'\n';
        else
            g<<CB2(1,N,val)<<'\n';}

    return 0;
}