#include <bits/stdc++.h>
using namespace std;
ifstream f ( "cautbin.in" ); ofstream g ( "cautbin.out" );
int main()
{   int p,c,x,m,n,v[100006]={0};
    f>>n;
    for(int i=1;i<=n;i++) f>>v[i];
    f>>m;
    while(m--)
    {   f>>c>>x;
        if(c==0)
        {   p=upper_bound(v+1,v+n+1,x)-v-1;
            if(p<=n and p>=1 and v[p]==x) g<<p<< '\n';
            else g<< "-1 \n";
        }
        else if(c==1)
        {   p=upper_bound(v+1,v+n+1,x)-v-1;
            g<<p<< '\n';
        }
        else
        {   p=lower_bound(v+1,v+n+1,x)-v;
            g<<p<< '\n';
        }
    }
    return 0;
}