#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100001];
int main()
{
    int n,gg,i,poz=0,j,a,b,k,u,p,m;
    in>>n;
    for(i=1; i<=n; i++)
        in>>v[i];
    in>>gg;
    for(j=1; j<=gg; j++)
    {
        in>>a>>b;
        if(a==0)
        {
            p=1;
            u=n;
            k=-1;
            if(v[u]==b)
                out<<u<<'\n';
            else
            {
                while(p<=u)
                {
                    m=(p+u)/2;
                    if(v[m]==b && v[m+1]>b)
                    {
                        k=m;
                        break;
                    }
                    else if(v[m]>b)
                        u=m-1;
                    else
                        p=m+1;
                }
                out<<k<<'\n';
            }
        }
        else if(a==1)
        {
            u=n;
            p=1;
            if(b>=v[u])
            {
                out<<n<<'\n';
            }
            else
            {
                while(p<=u)
                {
                    m=(p+u)/2;
                    if(v[m]<=b && v[m+1]>b)
                    {
                        k=m;
                        break;
                    }
                    else if(v[m]<b)
                    {
                        p=m+1;
                    }
                    else
                        u=m-1;
                }
                out<<k<<'\n';
            }
        }
        else
        {
            p=1;
            u=n;
            if(b<=v[p])
                out<<p<<'\n';
            else
            {
                while(p<=u)
                {
                    m=(p+u)/2;
                    if(v[m]>=b && v[m-1]<b)
                    {
                        k=m;
                        break;
                    }
                    else if(v[m]<b)
                        p=m+1;
                    else
                        u=m-1;
                }
                out<<k<<'\n';
            }
        }
    }
    return 0;
}