#include <cstdio>
#define ll long long
using namespace std;
const int NMAX = 100000 ,L = 16 ;
ll v[NMAX] ;
ll n ;
ll caut0(ll x){
    ll pas = 1 << L ,r = 0 ;
    while (pas){
        if (r + pas <= n && v[r + pas] <= x)
            r += pas ;
        pas /= 2 ;
    }
    if (v[r] != x)
       r = -1 ;
    return r ;
}
ll caut1(ll x){
    ll pas = 1 << L , r = 0 ;
    while (pas){
        if (r + pas <= n && v[r + pas] <= x)
            r += pas ;
        pas /= 2 ;
    }
    return r ;
}
ll caut2(ll x){
    ll pas = 1 << L , r = 0 ;
    while(pas){
        if (r + pas <= n && v[r + pas] < x)
            r += pas ;
        pas /= 2 ;
    }
    r++;
    return r ;
}
int main()
{
    freopen("cautbin.in","r",stdin) ;
    freopen("cautbin.out","w",stdout) ;
    ll m ,a ,b ,i ;
    scanf("%lld",&n) ;
    for (i = 1 ; i <= n ; ++ i)
        scanf("%lld",&v[i]) ;
    scanf("%lld",&m) ;
    for (i = 0 ; i < m ; ++ i){
        scanf("%lld %lld" ,&a ,&b) ;
        if (a == 0)
            printf("%lld\n",caut0(b)) ;
        else if (a == 1)
            printf("%lld\n",caut1(b)) ;
        else printf("%lld\n",caut2(b)) ;
    }
    return 0;
}