//Rares 0net
#ifdef RS
#define RS
#endif
using namespace std;
#ifdef RS
    #include "Rares0.hpp"
#else
    #include<vector>
    #include<fstream>
    const string N_file="cautbin";
    ifstream fin(N_file+".in");
    ofstream fout(N_file+".out");
    #define cin fin
    #define cout fout
    #define endl "\n"
#endif
void RSinit()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
}
#define INF 0x3f3f3f3f
int n, Q;
vector<int>v;
int BSfor0(int val)
{
    int i, lg;
    for(lg=1; lg<=n; lg<<=1)
        ;
    for(i=0; lg; lg>>=1)
        if(i+lg<=n && v[i+lg]<=val)
           i+=lg;
    return v[i]==val ? i : -1;
}
int BSfor1(int val)
{
    int i, lg;
    for(lg=1; lg<=n; lg<<=1)
        ;
    for(i=0; lg; lg>>=1)
        if(i+lg<=n && v[i+lg]<=val)
           i+=lg;
    return i;
}
int BSfor2(int val)
{
    int i, lg;
    for(lg=1; lg<=n; lg<<=1)
        ;
    for(i=n; lg; lg>>=1)
        if(i-lg>0 && v[i-lg]>=val)
            i-=lg;
    return i;
}
void Read()
{
    cin>>n;
    v.resize(n);
    for(int &nr:v)
        cin>>nr;
    v.insert(v.begin(), INF);
}
void Solve()
{
    cin>>Q;
    for(int index=1; index<=Q; ++index)
    {
        int var;
        int nr;
        cin>>var>>nr;
        switch(var)
        {
            case 0:
                cout<<BSfor0(nr)<<endl; break;
            case 1:
                cout<<BSfor1(nr)<<endl; break;
            case 2:
                cout<<BSfor2(nr)<<endl; break;
        }
    }
}
main()
{
    RSinit();
    Read();
    Solve();
}