#include<stdio.h>
using namespace std;

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

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

void read()
{
    scanf("%d", &n);
    for(int i = 1; i<=n; i++)
        scanf("%d", &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()
{
    scanf("%d", &m);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d", &x);
        scanf("%d", &y);
        if(x == 0)
        {
            printf("%d\n",bsearch0(1,n,y));
        }
        else if(x == 1)
        {
            printf("%d\n",bsearch1(1,n,y));
        }
        else
        {
            printf("%d\n",bsearch2(1,n,y));
        }

    }

}

int main()
{
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    read();
    solve();

    return 0;
}