#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("cautbin.in");
ofstream g ("cautbin.out");
int st,dr,mij,n,i,j,k,x,v[100001],p,y,b;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>p;
    for(i=1;i<=p;i++)
    {
        f>>y>>x;
        if(y==0)
        {
        b=upper_bound(v+1,v+n+1,x)-v-1;
        if(b>=1&&b<=n&&v[b]==x) g<<b<<'\n';
        else g<<-1<<'\n';
        }
        else if(y==1)
        {
        b=lower_bound(v+1,v+n+1,x+1)-v-1;
        g<<b<<'\n';
        }
        else
        {
        b=upper_bound(v+1,v+n+1,x-1)-v-1;
        g<<b<<'\n';
        }
    }
    return 0;
}