#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;


void open(){
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
}

int n,q,type,b,x[100010],lo,mid,hi,ans;

int main(){
    open();
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&x[i]);
    scanf("%d",&q);
    for (int i=0;i<q;i++){
        scanf("%d%d",&type,&b);
        ans=-1;
        if (type==0){
            lo=1;hi=n;
            while (1){
                mid=(lo+hi)>>1;
                if (x[mid]<=b){
                    ans=mid;
                    lo=mid+1;
                }
                else {
                    hi=mid-1;
                }
                if (lo>hi) break;
            }
            if (x[ans]!=b){
                ans=-1;
            }
        }
        else if (type==1){
            lo=1;hi=n;
            while (1){
                mid=(lo+hi)>>1;
                if (x[mid]<=b){
                    ans=mid;
                    lo=mid+1;
                }
                else {
                    hi=mid-1;
                }
                if (lo>hi) break;
            }
        }
        else {
            lo=1;hi=n;
            while (1){
                mid=(lo+hi)>>1;
                if (x[mid]<b){
                    lo=mid+1;
                }
                else {
                    ans=mid;
                    hi=mid-1;
                }
                if (lo>hi) break;
            }
        }
        printf("%d\n",ans);
    }
    //system("pause");
    return 0;
}