#include <bits/stdc++.h>
using namespace std;
 
int n,m,i,x,y,a[100100];
 
int main(){
    ifstream cin ("cautbin.in");
    ofstream cout ("cautbin.out");
    cin>>n;
    for (i=1; i<=n; i++) cin>>a[i];
    cin>>m;
    for (i=1; i<=m; i++){
        cin>>x>>y;
        if (x==0){
            if (a[n]<y) cout<<"-1";
            else if (a[1]>y) cout<<"-1";
            else {
                int st=1, dr=n, mid=st+ (dr-st)/2;
                while (dr-st>1){
                    if (y>=a[mid]){
                        st=mid; mid=st+ (dr-st)/2;
                    }
                    else {
                        dr=mid-1; mid=st+(dr-st)/2;
                    } 
                }
                if(a[dr]==y) cout<<dr;
                else if (a[st]==y) cout<<st<<"\n";
                else cout<<"-1\n";
            }
        }
        else if (x==1){
            int st=1, dr=n, mid=st+ (dr-st)/2;
            while (dr-st>1){
                if (y>=a[mid]){
                    st=mid; mid=st+ (dr-st)/2;
                }
                else {
                    dr=mid-1; mid=st+(dr-st)/2;
                } 
            }
            if(a[dr]<=y) cout<<dr<<"\n";
            else cout<<st<<"\n";
        }
        else {
            int st=1, dr=n, mid=st+ (dr-st)/2;
                while (dr-st>1){
                    if (y>a[mid]){
                        st=mid; mid=st+ (dr-st)/2;
                    }
                    else {
                        dr=mid; mid=st+(dr-st)/2;
                    } 
                }
                if (a[st]>=y) cout<<st<<"\n";
                else cout<<dr<<"\n";
        }
    }
    return 0;
}