#include <fstream>

using namespace std;
int v[100001];
int main()
{
    int n, x, m, tip;
    ifstream f ("cautbin.in");
    ofstream g ("cautbin.out");
    f>>n;
    for(int i=1; i<=n; i++)
    {
        f>>x;
        v[i]=x;
    }
    f>>m;
    for(int i=1; i<=m; i++)
    {
        f>>tip>>x;
        if(tip==0)
        {
            int st = 1, dr = n, pozMax = -1;
            while(st<=dr)
            {
                int mij = ( st + dr)/2;
                if(v[mij] == x)
                {
                    pozMax = mij;
                    st = mij + 1;
                }
                ///
                /// 1 2 2 5 5 6 6 8 9
                else if(v[mij] < x)
                {
                    st = mij + 1;
                }
                else
                {
                    dr = mij -1;
                }
            }
            g<<pozMax<<'\n';
        }
        else if(tip == 1)
        {
            int st = 1, dr = n, pozMax = 1, mij;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(v[mij] <= x)
                {
                    pozMax = mij;
                    st = mij + 1;
                }
                else
                {
                    dr = mij - 1;
                }
            }
            g<<pozMax<<'\n';
        }
        else
        {
            int st=1, dr=n, pozMini, mij;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(v[mij]>=x)
                {
                    dr= mij-1;
                    pozMini=mij;
                }
                else
                {
                    st= mij+1;
                }
            }
            g<<pozMini<<'\n';
        }
    }
    return 0;
}