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

int n, m, a[100050];
int pb, caut;

void citire()
{
    scanf("%d\n", &n);
    for(int i = 1; i<=n; i++)
    {
        scanf("%d ", &a[i]);
    }
    scanf("\n");
}

int p1(int x)
{
    int st = 1, dr = n, mij, poz = -1;
    while(st <= dr)
    {
        mij = (st + dr)/2;
        if(a[mij] <= x)
        {
            if(a[mij] == x)
            {
                poz = mij;
            }
            st = mij+1;
        }
        else
        {
            dr = mij-1;
        }
    }
    return poz;
}

int p2(int x)
{
    int st = 1, dr = n, mij, poz = -1;
    while(st <= dr)
    {
        mij = (st + dr)/2;
        if(a[mij] <= x)
        {
            poz = mij;
            st = mij+1;
        }
        else
        {
            dr = mij-1;
        }
    }
    return poz;
}

int p3(int x)
{
    int st = 1, dr = n, mij, poz = -1;
    while(st <= dr)
    {
        mij = (st + dr)/2;
        if(a[mij] < x)
        {
            st = mij+1;
        }
        else
        {
            poz = mij;
            dr = mij-1;
        }
    }
    return poz;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    citire();
    scanf("%d\n", &m);
    for(int i = 1; i<=m; i++)
    {
        scanf("%d %d\n", &pb, &caut);
        if(pb == 0)
            printf("%d\n", p1(caut));
        else if(pb == 1)
            printf("%d\n", p2(caut));
        else
            printf("%d\n", p3(caut));
    }
    return 0;
}