//
//  main.c
//  cautbin
//
//  Created by Alexandru Bâgu on 1/7/14.
//  Copyright (c) 2014 Alexandru Bâgu. All rights reserved.
//

#include <stdio.h>

int binsea0(int *v, int n, int x)
{
    int i, k = 1 << 30;
    for(i = 0; i <= n && k > 0; k >>= 1)
        if(i + k <= n)
            if(v[i + k] <= x)
                i += k;
    return i;
}
int binsea1(int *v, int n, int x)
{
    int i = binsea0(v, n, x);
    if(v[i] != x) return -1;
    return i;
}

int binsea2(int *v, int n, int x)
{
    int i = binsea0(v, n, x);
    while(v[i] >= x) i--;
    return i + 1;
}

int main(int argc, const char * argv[])
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    int n, i, q;
    scanf("%d", &n);
    int *v = (int*)malloc((n + 1) * sizeof(int));
    for(i = 1; i <= n; i++)
        scanf("%d", v + i);
    scanf("%d", &q);
    int a, x;
    for(i = 0; i < q; i++)
    {
        scanf("%d %d", &a, &x);
        if(a == 0) printf("%d\n", binsea1(v, n, x));
        else if(a == 1) printf("%d\n", binsea0(v, n, x));
        else printf("%d\n", binsea2(v, n, x));
    }
    return 0;
}