#include <fstream>
 
using namespace std;
ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");
int const NM = 100001;
int v [NM] , n;
inline int c1 (int x){
    int pas = (1 << 16) , found = 0;
    while (pas){
        if (found + pas <= n && v [found + pas] <= x)
            found += pas ;
        pas /= 2;
    }
    if (v[found] < x)
        return -1;
    return found;
}
inline int c2 (int x){
    int pas = (1 << 16) , found = 0;
    while (pas){
        if (found + pas <= n && v [found + pas] <= x)
            found += pas;
        pas /= 2;
    }
    return found;
}
inline int c3 (int x){
    int pas = (1 << 16) , found = 0;
    while (pas){
        if (pas + found <= n && v [pas + found] < x)
            found += pas;
        pas /= 2;
    }
    return 1 + found;
}
int main()
{
    int i;
    cin >> n;
    for(i = 1 ; i <= n ; ++ i)
        cin >> v [i];
    int q;
    cin >> q;
    for (i = 1 ; i <= q ; ++ i){
        int c , x;
        cin >> c >> x;
        if (! c)
            cout << c1 (x) << '\n';
        else
            if (c == 1)
                cout << c2 (x) << '\n';
            else
                cout << c3 (x) << '\n';
    }
    return 0;
}