#include <bits/stdc++.h>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m,a[100005];

int findPos(int val) {
    int mid,lo=0,hi=n+1;
    while(hi-lo>1) {
        mid=(hi+lo)>>1;
        if(a[mid]<=val) {
            lo=mid;
        } else {
            hi=mid;
        }
    }
    if(a[lo]!=val) return -1;
    else return lo;
}

int lowerBound(int val) {
    int mid,lo=0,hi=n+1;
    while(hi-lo>1) {
        mid=(hi+lo)>>1;
        if(a[mid]<=val) {
            lo=mid;
        } else {
            hi=mid;
        }
    }
    return lo;
}

int upperBound(int val) {
    int mid,lo,hi=n+1;
    while(hi-lo>1) {
        mid=(hi+lo)>>1;
        if(a[mid]>=val) {
            hi=mid;
        } else {
            lo=mid;
        }
    }
    return hi;
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++) {
        fin>>a[i];
    }
    fin>>m;
    for(int i=1;i<=m;i++) {
        int x,val;
        fin>>x>>val;
        switch(x) {
        case 0:
            fout<<findPos(val);
            break;
        case 1:
            fout<<lowerBound(val);
            break;
        case 2:
            fout<<upperBound(val);
            break;
        }
        fout<<'\n';
    }
    return 0;
}