#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define N 100010
using namespace std;
int v[N];//={0,1,1,1,2,3,3,3,5,5,5,7};
///0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
int bsearch0 (int st, int dr, int x)
{
    int m,poz=-1;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]<=x)
        {
            poz=m;
            st=m+1;
        }
        else
        {
            dr=m-1;
        }
    }
    if(v[poz]!=x)
        poz=-1;
    return poz;

}
///1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x

int bsearch_ultim (int st, int dr, int x)
{
   int m,poz;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]<=x)
        {
            poz=m;
            st=m+1;
        }
        else
        {
            dr=m-1;
        }
    }

    return poz;
}
///2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x

int bsearch_prim (int st, int dr, int x)
{
   int m,poz;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]>=x)
        {
            poz=m;
            dr=m-1;
        }
        else
        {
            st=m+1;
        }
    }

    return poz;
}

int main ()
{
    int i, n, m, tip, val;

    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);

    scanf("%d", &m);
    while (m --)
    {
        scanf("%d%d", &tip, &val);
        if (tip == 0)
            printf("%d\n", bsearch0(1, n, val));
        if (tip == 1)
            printf("%d\n", bsearch_ultim(1, n, val));
        if (tip == 2)
            printf("%d\n", bsearch_prim(1, n, val));
    }
    exit(0);
}