#include <iostream>
#include <fstream>

using namespace std;

int num[100005];

int caut(int st, int dr, int val){
    int mid;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(num[mid] < val)
            st = mid + 1;
        if(num[mid] > val)
            dr = mid - 1;
        if(num[mid] == val)
            return mid;
    }
    return -1;
}

int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int n;
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> num[i];
    int m, op, x;
    fin >> m;
    for(int q = 1; q <= m; ++q){
        fin >> op >> x;
        int mid = caut(1, n, x);
        if(op == 0){
            if(mid == -1)
                fout << -1;
            else{
                while(num[mid] == x && mid <= n)
                    mid++;
                mid--;
                fout << mid;
            }
        }
        if(op == 1){
            if(mid == - 1){
                int val = x - 1;
                while(caut(1, n, val) == -1 && val > 0)
                    val--;
                val++;
                mid = caut(1, n, val);
                while(num[mid] == val && mid <= n)
                    mid++;
                mid--;
            }
            else{
                while(num[mid] == x && mid <= n)
                    mid++;
                mid--;
            }
            fout << mid;
        }
        if(op == 2){
            if(mid == -1){
                int val = x + 1;
                while(caut(1, n, val) == -1)
                    val++;
                val--;
                mid = caut(1, n, val);
                while(num[mid] == val && mid > 0)
                    mid--;
                mid++;
            }
            else{
                while(num[mid] == x && mid > 0)
                    mid--;
                mid++;
            }
            fout << mid;
        }
        fout << "\n";
    }
    return 0;
}