#include <fstream>

using namespace std;

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

int v[100005];
int main(){
    int n, cerinta, val, m;

    fin>>n;
    for(int i = 1; i <= n; i++)
        fin>>v[i];
    
    fin>>m;
    for(int i = 0; i < m; i++) {
        fin>>cerinta>>val;

        int st = 1;
        int dr = n + 1;
        while(st + 1 < dr) {
            int mij = (st + dr) / 2;

            if(v[mij] <= val)
                st = mij;
            else 
                dr = mij;
        }

        if(cerinta == 0) {
            if(v[st] != val)
                fout<<-1<<endl;
            else 
                fout<<st<<endl;
        }
        else if(cerinta == 1) 
            fout<<st<<endl;
        else {
            int st = 0;
            int dr = n;
            while(st + 1 < dr) {
                int mij = (st + dr) / 2;

                if(v[mij] < val)
                    st = mij;
                else 
                    dr = mij;
            }

            fout<<dr<<endl;
        }
    }
    return 0;
}