#include <fstream>
#include <algorithm>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int f[100000];
int sp[100000];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>f[i];
    }
    int x;
    cin>>x;
    for(int i=0;i<x;i++){
        int c,nr;
        cin>>c>>nr;
        if(c==0||c==1){

            int dr=upper_bound(f,f+n,nr)-f-1;
            ///cout<<upper_bound(f,f+n,nr)-f<<endl;
            if(f[dr]==nr||c==1){
                cout<<dr<<endl;
            }
            else cout<<-1<<endl;
        }
        else {
            int dr=lower_bound(f,f+n,nr)-f;
             cout<<dr<<endl;
        }
    }
    return 0;
}