#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main()
{
    int n,x;
    fin >> n;
    int a[n+1];
    for (int i=1;i<=n;i++)
    {
        fin >> a[i];
    }
    fin >> x;
    int b[x+1],c[x+1];
    for (int i=1;i<=x;i++)
    {
        fin >> c[i];
        fin >> b[i];
        int mid,ans,st,dr;
        st=1;
        dr=n;
        mid=(st+dr)/2+(st+dr)%2;
        if (c[i]==0)
        {
            ans=-1;
            while (st<=dr)
            {
                if (a[mid]>b[i])
                {
                    dr=mid-1;
                }
                else
                {
                    st=mid+1;
                    if (a[mid]==b[i]) ans=mid;
                }
                mid=(st+dr)/2 + (st+dr)%2;
            }
            fout << ans << endl;
        }
        else if (c[i]==1)
        {
            while (st<dr)
            {
                if (a[mid]>b[i])
                {
                    dr=mid-1;
                }else
                {
                    st=mid;
                    ans=mid;
                }
                mid=(st+dr)/2+ (st+dr)%2;
            }
            fout << ans << endl;
        }
        else
        {
            while (st<dr)
            {
                if (a[mid]>=b[i])
                {
                    dr=mid;
                    ans=mid;
                }else
                {
                    st=mid+1;
                }
                mid=(st+dr)/2;
            }
            fout << ans << endl;
        }
    }
    return 0;
}