#include <stdio.h>
using namespace std;
int i, n, v[100001], m, x, y;


int caut0( int key )
    //int mij;
    {
    int mid, st = 1, dr = n;
        while (st <= dr) {
            mid = (st + dr) / 2;
            if (v[mid] <= key) st = mid + 1;
            if (v[mid] > key) dr = mid - 1;
        }
        mid=(st + dr) / 2;
        if (v[mid]>key) --mid;
        if (v[mid]=key) return mid;
        return -1;
    }
int caut1( int key )
    //int mij;
    {
    int mid, st = 1, dr = n;
        while (st < dr) {
            mid = (st + dr) / 2;
            if (v[mid] <= key) st = mid + 1;
            if (v[mid] > key) dr = mid;
        }
        mid = (st + dr) / 2;
        if (v[mid]>key) --mid;
        return mid;
    }

int caut2( int key )
    //int mij;
    {
    int mid, st = 1, dr = n;
        while (st < dr) {
            mid = (st + dr) / 2;
            if (v[mid] < key) st = mid + 1;
            if (v[mid] >= key) dr = mid;
        }
        mid=(st + dr) / 2;
        if (v[mid]<key) ++mid;
        return mid;
    }



int main()
{
    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);
    for (i=1;i<=m;i++){
        scanf("%d%d",&y,&x);
        if (y==0) printf("%d\n",caut0( x ));
        if (y==1) printf("%d\n",caut1( x ));
        if (y==2) printf("%d\n",caut2( x ));
    }
    return 0;
}