#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int a[100100],x,y,m,n,i;
int main()
{
    fin>>n;
    for(i=1;i<=n;i++) fin>>a[i];
    fin>>m;
    while(m--)
    {
        fin>>y>>x;
        if(y==0)
        {
            y=upper_bound(a+1,a+n+1,x)-(a+1);
            if(a[y]==x && y!=1) fout<<y<<"\n";
                 else fout<<"-1\n";
        }
        if(y==1) fout<<upper_bound(a+1,a+n+1,x)-(a+1)<<"\n";
        if(y==2)fout<<lower_bound(a+1,a+n+1,x)-a<<"\n";
    }
}