#include <bits/stdc++.h>

std :: ifstream in ("cautbin.in");
std :: ofstream out ("cautbin.out");

const int NMAX = 1e5 + 5;


int n, m;

int v[NMAX];

int cer;

int val;

void cautbin()
{
    int st = 1;
    int dr = n;
    int ret = -1;

    while(st <= dr)
    {
        int mij = (st + dr) / 2;

        if(v[mij] > val)
        {
            dr = mij - 1;
        }
        else if(v[mij] < val)
        {
            st = mij + 1;
        }
        else
        {
            ret = mij;
            st = mij + 1;
        }
    }

    out << ret << '\n';
}

void cautbin1()
{
    int st = 1;
    int dr = n;
    int ret = 0;

    while(st <= dr)
    {
        int mij = (st + dr) / 2;

        if(v[mij] <= val)
        {
            ret = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }

    out << ret << '\n';
}

void cautbin2()
{
    int st = 1;
    int dr = n;
    int ret = 0;

    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(v[mij] < val)
        {
            st = mij + 1;
        }
        else
        {
            ret = mij;
            dr = mij - 1;
        }
    }

    out << ret << '\n';
}


int main()
{

    std :: ios_base :: sync_with_stdio(false);
    in.tie(NULL);

    in >> n;

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

    in >> m;

    while(m --)
    {
        in >> cer >> val;

        if(!cer)
        {
            cautbin();
        }
        else if (cer == 1)
        {
            cautbin1();
        }
        else
        {
            cautbin2();
        }
    }

    return 0;
}