#include <stdio.h>
#include<stdlib.h>
#define N 100010
int v[N];
int bsearch0(int s, int d, int key){
    int m;
    while(s<=d){
        m = (s+d)/2;
        if(v[m]<=key)
            s = m + 1;
        else
            d = m - 1;
    }
    m = (s+d)/2;
    if(v[m]> key) m--;
    if (v[m]==key)
        return m;
    return -1;
}
int bsearch1(int s, int d, int key){
    int m;
    while(s<d){
        m = (s+d)/2;
        if(v[m]<=key)
            s= m+1;
        else
            d=m;
    }
    m = (s+d)/2;
    if(v[m]>key)
        --m;
    return m;
}
int bsearch2(int s, int d, int key){
    int m;
    while(s<d){
        m = (s+d)/2;
        if(v[m]<key)
            s= m+1;
        else
            d=m;
    }
    m = (s+d)/2;
    if(v[m]<key)
        ++m;
    return m;
}
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", bsearch1(1, n, val));
          if (tip == 2)
             printf("%d\n", bsearch2(1, n, val));
    }
    return 0;
}