#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int C0(long long a[100001],int n,long long x)
{
    if(a[upper_bound(a+1,a+n+1,x)-a-1]!=x) return -1;
    else return upper_bound(a+1,a+n+1,x)-a-1;
}
int C1(long long a[100001],int n,long long x)
{
    if(a[upper_bound(a+1,a+n+1,x)-a-1]==x) return upper_bound(a+1,a+n+1,x)-a-1;
    else return lower_bound(a+1,a+n+1,x)-a-1;
}
int C2(long long a[100001],int n,long long x)
{
    return lower_bound(a+1,a+n+1,x)-a;
}
long long v[100001],cer,nr,i,m,j,n;
int main()
{
    f>>n;
    for(i=1; i<=n; i++) f>>v[i];
    f>>m;
    for(j=1; j<=m; j++)
    {
        f>>cer>>nr;
        if(cer==0) g<<C0(v,n,nr)<<'\n';
        else if(cer==1) g<<C1(v,n,nr)<<'\n';
        else g<<C2(v,n,nr)<<'\n';
    }

    return 0;
}