#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int main()
{
    int inf = 2147483647;
    int n,v[100010],p,x,m,i,st,dr,mij;
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    in>>p;
    v[0] = -inf;
    v[n+1] = inf;
    for(i=1;i<=p;i++)
        {
            in>>m>>x;
            if(m==0)
            {
                st=0;
                dr=n+1;
                while(dr-st>1)
                {
                     mij=(st+dr)/2;
                     if(v[mij]<=x)
                        st=mij;
                     else dr=mij;
                }
                if(v[st]<x)  out<<"-1";
                       else out<<st<<"\n";
}
            if(m==1)
            {
                st=0;
                dr=n+1;
                while(dr-st>1)
                {
                     mij=(st+dr)/2;
                     if(v[mij]<=x)
                        st=mij;
                     else dr=mij;
                }
            out<<st<<"\n";}
            if(m==2)
            {
                st=0;
                dr=n+1;
                while(dr-st>1)
                {
                     mij=(st+dr)/2;
                     if(v[mij]>=x)
                        dr=mij;
                     else st=mij;
                }
                out<<dr<<"\n";
            }


        }
        return 0;
}