#include<bits/stdc++.h>
using namespace std;

long int a[100100],x;
int m,q,n;


int cautbin1(long x,int l, int r){
    int mid;
    while(l<r){
        mid=(l+r+1)/2;
        if(x<a[mid]) r=mid-1;
            else l=mid;
    }
    if(a[l]!=x && a[r]!=x) return -1;
    if(a[l]==x) {while(a[l+1]==x && l+1<=n) l++; return l;}
    if(a[r]==x) {while(a[r+1]==x && r+1<=n) r++; return r;}
}

int cautbin2(long x,int l, int r){
    int mid;
    while(l<r){
        mid=(l+r+1)/2;
        if(a[mid]<=x) l=mid;
            else r=mid-1;
    }
    while(a[r+1]<=x && r+1<=n) r++; return r;
}

int cautbin3(long x,int l, int r){
    int mid;
    while(l<r){
        mid=(l+r)/2;
        if(a[mid]>=x) r=mid;
            else l=mid+1;
    }
    while(a[r-1]>=x && r-1>=1) r--; return r;
}


int main(){

    ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");

    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    cin>>m;

    for(int go=1;go<=m;go++){
        cin>>q>>x;
        if(q==0) cout<<cautbin1(x,1,n)<<'\n';
            else if(q==1) cout<<cautbin2(x,1,n)<<'\n';
                else cout<<cautbin3(x,1,n)<<'\n';
    }



}