#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
const int maxn=100005;
int n,m,v[100005];
int cautbin1(int x)
{   int st=1,dr=n,rez=-1;
    while(st<=dr)
    {   int mij=(st+dr)/2;
        if(v[mij]<=x)
        {   rez=mij;
            st=mij+1;
        }
        else dr=mij-1;
    }
    return rez;
}
int cautbin2(int x)
{   int st=1,dr=n,rez=-1;
    while(st<=dr)
    {   int mij=(st+dr)/2;
        if(v[mij]>=x)
        {   rez=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }
    return rez;
}
int main()
{   f>>n;
    for(int i=1;i<=n;i++) f>>v[i];
    f>>m;
    for(int i=1;i<=m;i++)
    {   int op,x;
        f>>op>>x;
        if(op==0)
        {   int rez=cautbin1(x);
            if(rez==-1) g<<-1;
            else if(v[rez]!=x) g<<-1;
                else g<<rez;
        }
        else if(op==1) g<<cautbin1(x);
            else g<<cautbin2(x);
        g<<'\n';
    }
    f.close(); g.close();
    return 0;
}