#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>

#define x first
#define y second
#define ll long long
#define pb push_back
#define bg begin()
#define ed end()
#define cl clear()
#define pii pair<int, int>

#define int ll

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

const int MOD = 1e9 + 7;
const char nl = '\n';
const int NMAX = 1e5 + 5;
const int INF = 1e9;

int n, v[NMAX];

signed main()
{
    in >> n;
    for(int i = 1; i <= n; ++i)
        in >> v[i];
    int q, x, c;
    in >> q;
    while(q--){
        in >> c >> x;
        int l = 1, r = n, sol = -1;
        if(c == 0){
            while(l <= r){
                int mid = (l + r) / 2;
                if(v[mid] == x){
                    sol = mid;
                    l = mid + 1;
                }
                else{
                    if(v[mid] < x)
                        l = mid + 1;
                    else
                        r = mid - 1;
                }
            }
            out << sol << nl;
        }
        else if(c == 1){
            while(l <= r){
                int mid = (l + r) / 2;
                if(v[mid] <= x){
                    sol = mid;
                    l = mid + 1;
                }
                else
                    r = mid - 1;
            }
            out << sol << nl;
        }
        else{
             while(l <= r){
                int mid = (l + r) / 2;
                if(v[mid] >= x){
                    sol = mid;
                    r = mid - 1;
                }
                else
                    l = mid + 1;
            }
            out << sol << nl;
        }
    }
    return 0;
}