#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main()
{int n,i,v[100001],c,x,y,m;
f>>n;
for(i=1;i<=n;i++)
{f>>v[i];

}
f>>m;
for(i=1;i<=m;i++)
{f>>x>>y;
    if(x==0)
    {c=upper_bound(v+1,v+n+1,y)-v-1;
     if(v[c]!=y)
        g<<"-1"<<'\n';
     else
        g<<c<<'\n';
    }
    else if(x==1)
    {c=upper_bound(v+1,v+n+1,y)-v-1;
        if(v[c]!=y)
            g<<c-1<<'\n';
        else g<<c<<'\n';
    }
    else
    {c=lower_bound(v+1,v+n+1,y)-v;
        if(v[c]==y)
            g<<c<<'\n';

    }
}



    return 0;
}