#include <fstream>

using namespace std;
int x[100001];
int begin, end, n, mid;
bool ok;
ofstream out ("cautbin.out", ofstream::out);

void solve (int y, int s) {
    begin = 0, end = n - 1;
    while (end - begin > 1)
    {
        mid = begin + (end - begin)/2;
        if (y == 0)
        {
            if (x[mid] > s)
                end = mid - 1;
            else
                begin = mid;
        }
        else if (y == 1)
        {
            if (x[mid] > s)
                end = mid;
            else
                begin = mid;
            if (end - begin <= 1)
            {
                if (x[end] == s)
                    out << end + 1 << endl;
                else if (x[begin] == s)
                    out << begin + 1 << endl;
                else if (x[end] < s)
                    out << end + 1 << endl;
                else out << begin + 1 << endl;
            }
        } else if (y == 2)

        {
            if (x[mid] > s)
                end = mid;
            else
                begin = mid;
            if (end - begin <= 1)
            {
                if (x[begin] == s)
                    out << begin + 1 << endl;
                else if (x[end] == s)
                    out << end + 1 << endl;
                else if (x[begin] > s)
                    out << begin + 1 << endl;
                else out << end + 1 << endl;
            }
        }
    }
    if (y == 0)
    {
        if (begin == end && x[begin] == s)
            out << begin + 1 << endl;
        else if (begin == end && x[begin] != s)
            out << -1 << endl;
        else if (begin != end)
        {
            if (x[begin + 1] == s)
                out << begin + 2 << endl;
            else if (x[begin] == s)
                out << begin + 1 << endl;
            else out << -1 << endl;
        }
    }

}

int solve2 (int y, int s) {

    begin = 0;
    end = n;
    while (begin  + 1 < end) {
        mid = begin + (end - begin)/2;
        if (x[mid] >= s) {
            end = mid - 1;
        }
        else {
            begin = mid;
        }
    }

    if (x[end] < s)
        end++;
    if (end == -1)
        end++;

    return end + 1;
}

int solve1 (int y, int s) {

    begin = 0;
    end = n;
    while (begin < end) {
        mid = begin + (end - begin)/2;
        if (x[mid] <= s) {
            begin = mid + 1;
        }
        else {
            end = mid;
        }
    }

    if (x[end] > s)
        end--;
    if (end == n)
        end--;
    return end + 1;
}

int solve0 (int y, int s) {

    begin = 0;
    end = n;
    while (begin < end) {
        mid = begin + (end - begin)/2;
        if (x[mid] <= s) {
            begin = mid + 1;
        }
        else {
            end = mid;
        }
    }

    if (x[end] != s && x[end-1] != s)
        return -1;
    if (x[end - 1] == s)
        end--;

       return end + 1;
}

int main () {
    int q, y, s;
//    ifstream in ("cautbin.in", ifstream::in);
    freopen ("cautbin.in", "r", stdin);


//    in >> n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
//      in >> x[i];
        scanf("%d", &x[i]);
    }
    scanf("%d", &q);
//    in >> q;
    while (q--)
    {
        //in >> y >> s;
        scanf ("%d %d", &y, &s);
        if (y == 0)
           out << solve0 (y, s) << endl;
        else if (y == 1)
           out << solve1 (y, s) << endl;
        else 
           out << solve2 (y, s) << endl;
    }
}