#include <bits/stdc++.h>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int v[100005], n, m;

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

int caut_bin0(int x)
{
    int st = 1, dr = n, r = -1, mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] == x)
        {
            r = mij;
            st = mij + 1;
        }
        else if(v[mij] > x)
        {
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    return r;
}

int caut_bin1(int x)
{
    int st = 1, dr = n, r = -1, mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] <= x)
        {
            r = mij;
            st = mij + 1;
        }
        else if(v[mij] > x)
        {
            dr = mij - 1;
        }
    }
    return r;
}

int caut_bin2(int x)
{
    int st = 1, dr = n, r = -1, mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] >= x)
        {
            r = mij;
            dr = mij - 1;
        }
        else if(v[mij] < x)
        {
            st = mij + 1;
        }
    }
    return r;
}

void rezolva()
{
    int tip, x;
    fin >> m;
    while(m--)
    {
        fin >> tip >> x;
        if(tip == 0)
        {
            fout << caut_bin0(x) << '\n';
        }
        else if(tip == 1)
        {
            fout << caut_bin1(x) << '\n';
        }
        else if(tip == 2)
        {
            fout << caut_bin2(x) << '\n';
        }

    }
}


int main()
{
    citire();
    rezolva();
    return 0;
}