#include <bits/stdc++.h>
using  namespace std;

int a[100005],n;
int c0(int x){
    int st = 1,dr = n, mid =0 , poz = 0;
    while(st <= dr){
        mid = (st + dr) >> 1;
        if(a[mid] <= x){
            poz = mid;
            st = mid + 1;
        }else dr = mid - 1;
    }
    if(a[poz] != x)return -1;
    return poz;
}

int c1(int x){
    int st = 1, dr = n, mid =0 , poz =0 ;
    while(st <= dr){
        mid = (st + dr) >> 1;
        if(a[mid] <= x){
            st = mid + 1;
            poz = mid;
        }else
            dr = mid - 1;
    }
    return poz;

}
int c2(int x){
    int st = 1, dr=  n, mid= 0, poz;
    while(st <= dr){
        mid = (st + dr) >> 1;
        if(a[mid] >= x){
            poz =  mid;
            dr = mid-1;
        }else{
            st = mid + 1;
        }
    }
    return poz;
}

int main(void){
    ofstream cout("cautbin.out");
    ifstream cin("cautbin.in");
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
    }
    int Q;
    cin >> Q;
    while(Q--){
        int c, x;
        cin >> c>> x;
        if(c == 0)cout << c0(x) << '\n';
        else if(c == 1)cout << c1(x) << '\n';
        else cout << c2(x) << '\n';
    }
}