#include <fstream>

using namespace std;

int n,m2,i,v[100002],x,y,m,p,u;

ifstream fin ("cautbin.in");

ofstream fout ("cautbin.out");

int main (){

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];
    fin>>m2;
    for (i=1;i<=m2;i++){
        fin>>x>>y;
        if (x == 0){
            p = 1;
            u = n;
            while (p<=u){
                m = (p+u)/2;
                if (v[m]<=y)
                    p = m+1;
                else
                    u = m-1;
            }
            if (v[u] == y)
                fout<<u<<"\n";
            else
                fout<<-1<<"\n";
        }
        if (x == 1){
            p = 1;
            u = n;
            while (p<=u){
                m = (p+u)/2;
                if (v[m]<=y)
                    p = m+1;
                else
                    u = m-1;
            }
            fout<<u<<"\n";
        }
        if (x == 2){
            p = 1;
            u = n;
            while (p<=u){
                m = (p+u)/2;
                if (v[m] >= y)
                    u = m-1;
                else
                    p = m+1;
            }
            fout<<p<<"\n";
        }
    }


    return 0;
}