#include <iostream>
#include <fstream>
#define L_MAX 100001

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

int v[L_MAX], N, M, x;

int bsearch(int lo, int hi)
{
    if(lo > hi)
        return -1;
    else
    {
        int mid = lo + (hi - lo) / 2;
        //cout<<lo<<" "<<hi<< "  " << v[mid]<<endl;
        if(v[mid] == x)
        {
            if(bsearch(mid + 1, hi) == -1)
                return mid;
        }
        if(v[mid] <= x && lo != hi)
        {
            return bsearch(mid + 1, hi);
        }
        if(v[mid] > x && lo != hi)
        {
            return bsearch(lo, mid - 1);
        }
        return -1;
    }
}

int b1search(int lo, int hi)
{
    if(lo > hi)
        return -1;
    else
    {
        int mid = lo + (hi - lo) / 2;
        //cout<<lo<<" "<<hi<< "  " << v[mid]<<endl;
        if(v[mid] <= x)
        {
            if(b1search(mid + 1, hi) == -1)
                return mid;
        }
        if(v[mid] < x && lo != hi)
        {
            return b1search(mid + 1, hi);
        }
        if(v[mid] > x && lo != hi)
        {
            return b1search(lo, mid - 1);
        }
        return -1;
    }
}

int b2search(int lo, int hi)
{
    if(lo > hi)
        return -1;
    else
    {
        int mid = lo + (hi - lo) / 2;
        //cout<<lo<<" "<<hi<< "  " << v[mid]<<endl;
        if(v[mid] >= x)
        {
            if(b2search(lo, mid - 1) == -1)
                return mid;
        }
        if(v[mid] >= x && lo != hi)
        {
            return b2search(lo, mid - 1);
        }
        if(v[mid] < x && lo != hi)
        {
            return b2search(mid + 1, hi);
        }
        return -1;
    }
}


int main()
{
    in >> N;
    for(int i = 1; i <= N; i++)
        in >> v[i];
    in >> M;
    for(int i = 0; i < M; i++)
    {
        int t;
        in >> t;
        if(t == 0)
        {
            in >> x;
            out << bsearch(1, N) << "\n";
        }
        if(t == 1)
        {
            in >> x;
            out << b1search(1, N) << "\n";
        }
        if(t == 2)
        {
            in >> x;
            out << b2search(1, N) << "\n";
        }

    }
    in.close();
    out.close();
    return 0;
}