#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>

#define NMax 100005
#define mod 1999999973
#define INF 0x3f3f3f3f

using namespace std;
int p,x,n,m;
int a[NMax];

int cautbin1(int k){
    int lo = 1,hi = n, mij = 0;
    while(lo <= hi){
        mij = (lo + hi)/ 2;
        if(a[mij] == x && (mij + 1 > n || a[mij + 1] > x))
           return mij;
        else
        if(a[mij] <= x)
            lo = mij;
        else
        if(a[mij] > x)
            hi = mij + 1;
    }
    return -1;
}
int cautbin2(int k){
    int lo = 1,hi = n, mij = 0;
    while(lo <= hi){
        mij = (lo + hi)/ 2;
        if(a[mij] <= x && (mij + 1 > n || a[mij + 1] > x))
           return mij;
        else
        if(a[mij] <= x)
            lo = mij;
        else
        if(a[mij] > x)
            hi = mij + 1;
    }
    return -1;
}
int cautbin3(int k){
    int lo = 1,hi = n, mij = 0;
    while(lo <= hi){
        mij = (lo + hi)/ 2;
        if(a[mij] >= x && (mij - 1 < 1 || a[mij - 1] < x))
           return mij;
        else
        if(a[mij] < x)
            lo = mij - 1;
        else
        if(a[mij] >= x)
            hi = mij;
    }
    return -1;
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i){
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for(int i = 1; i <= m; ++i){
        scanf("%d%d",&p,&x);
        if(p == 0){
            printf("%d\n",cautbin1(x));
        }else
        if(p == 1){
            printf("%d\n",cautbin2(x));
        }else
        if(p == 2){
            printf("%d\n",cautbin3(x));
        }
    }

    return 0;
}