#include<iostream>
#include<fstream>
using namespace std;

#define MAXSIZE 100002
#define FIN "cautbin.in"
#define FOUT "cautbin.out"

ifstream f(FIN);
ofstream g(FOUT);

unsigned int v[MAXSIZE];
int n,m;

void read()
{
    f  >> n;
    for(int i = 1; i<=n; i++)
        f >> v[i];

}


int bsearch0(int left, int right, int value)
{
    while(left <= right )
    {
        if(left == right)
        {
            if(v[right] == value)
                return right;
            else return -1;
        }

        if(value >= v[(right+left) / 2])
        {
            left = (right+left) / 2;

        }

        if(value < v[(right+left) / 2])
        {
            right = (right+left) / 2;
        }

        if(right - left == 1)
        {
            if(value == v[right])
                return right;
            if(value == v[left])
                return left;
            else return -1;
        }
    }
}

int bsearch1(int left, int right, int value)
{
    while(left <= right )
    {
        if(left == right)
        {
           return left;
        }

        if(value >= v[(right+left) / 2])
        {
            left = (right+left) / 2;

        }

        if(value < v[(right+left) / 2])
        {
            right = (right+left) / 2;
        }

        if(right - left == 1)
        {
            if(v[right] <= value)
                return right;
            else return left;

        }
    }


}

int bsearch2(int left, int right, int value)
{
    while(left <= right )
    {
        if(left == right)
        {
           return left;
        }

        if(value > v[(right+left) / 2])
        {
            left = (right+left) / 2;

        }

        if(value <= v[(right+left) / 2])
        {
            right = (right+left) / 2;
        }

        if(right - left == 1)
        {
            if(v[left] >= value)
                return left;
            else return right;

        }
    }

}

void solve()
{
    f >> m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        f >> x;
        f >> y;
        if(x == 0)
        {
            g << bsearch0(1,n,y) << endl;
        }
        else if(x == 1)
        {
            g << bsearch1(1,n,y) << endl;
        }
        else
        {
            g << bsearch2(1,n,y) << endl;
        }

    }

}

int main()
{
    read();
    solve();

    return 0;
}