#include <bits/stdc++.h>

using namespace std;

int n,a[100005],m,c,x,mid,l,r;

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

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

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

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    in >> n;
    for(int i=1;i<=n;i++) in >> a[i];
    in >> m;
    for(int i=1;i<=m;i++){
        in >> c >> x;
        if(c==0) cout << 0, out << Bin0(x) << '\n';
        else if(c==1) cout << 1, out << Bin1(x) << '\n';
        else if(c==2) cout << 2, out << Bin2(x) << '\n';
    }
}