#include <fstream>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100010];
int main()
{
    int n,i,j,u,p,x,m,t,cer;
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    in>>t;
    for(i=1;i<=t;i++)
    {
        in>>cer>>x;
        p=1;
        u=n;
        if(cer==0)
        {
            while(p<=u)
            {
                m=(p+u)/2;
                if(v[m]<=x)
                    p=m+1;
                else
                    u=m-1;
            }
            m=(p+u)/2;
            if(v[m]>x)
                out<<m-1<<'\n';
            else if(v[m]==x)
                out<<m<<'\n';
            else if(v[m]<x)
                out<<"-1";
        }
        if(cer==1)
        {
           while(p<=u)
            {
                m=(p+u)/2;
                if(v[m]<=x)
                    p=m+1;
                else
                    u=m-1;
            }
            if(v[m]>x)
                out<<m-1<<'\n';
            else if(v[m]==x)
                out<<m<<'\n';
            else if(v[m]<x)
                out<<m<<'\n';
        }
        if(cer==2)
        {
            while(p<=u)
            {
                m=(p+u)/2;
                if(v[m]<x)
                    p=m+1;
                else
                    u=m-1;
            }
            if(v[m]>x)
                out<<m<<'\n';
            else if(v[m]==x)
                out<<m<<'\n';
            else if(v[m]<x)
                out<<m-1<<'\n';
        }
    }
}