#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define input "cautbin.in", "rt", stdin
#define output "cautbin.out", "wt", stdout
using namespace std;

const int nMax = 1e5;

int n, x, m;
int a[nMax];

int caut0(int l, int r)
{
    if (l > r) return -1;
    int mid = (l + r) / 2;
    if (x > a[mid] || (x == a[mid] && x == a[mid + 1])) return caut0(l + 1, r);
    if (x < a[mid]) return caut0(l, r - 1);
    return mid;
}

int caut1(int l, int r)
{
    int mid = (l + r) / 2;
    if (a[mid] > x) return caut1(l, r - 1);
    if (a[mid] <= x && a[mid + 1] <= x) return caut1(l + 1, r);
    return mid;
}

int caut2(int l, int r)
{
    int mid = (l + r) / 2;
    if (a[mid] < x) return caut2(l + 1, r);
    if (a[mid] >= x && a[mid - 1] >= x) return caut2(l, r - 1);
    return mid;
}

int caut(short int p)
{
    if (p == 0) return caut0(1, n);
    if (p == 1) return caut1(1, n);
    return caut2(1, n);
}

main()
{
    freopen(input);
    freopen(output);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    cin >> m;
    for (; m; --m)
    {
        short int p;
        cin >> p >> x;
        cout << caut(p) << "\n";
    }
}