#include <bits/stdc++.h>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n,m,a[100005],c,q,s;
int main()
{
    in>>n;
    for(int i=1; i<=n; ++i)
        in>>a[i];
    in>>m;
    for(int i=1; i<=m; ++i)
    {
        in>>c>>q;
        if(c==0)
        {
            int u=upper_bound(a+1,a+n+1,q)-a-1;
            if(a[u]!=q)
                out<<-1<<"\n";
            else out<<u<<"\n";
        }
        if(c==1)
        {
            int u=upper_bound(a+1,a+n+1,q)-a-1;
            while(a[u]>q)
                u--;
            out<<u<<"\n";
        }
        if(c==2)
        {
            int u=lower_bound(a+1,a+n+1,q)-a-1;
            while(a[u]<q)
                u++;
            out<<u<<"\n";
        }
    }
}