#include <iostream>
#include <fstream>
using namespace std;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
const int NMAX = 100001;
int v[NMAX];
int main()
{
    int n,m;
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>v[i];
    }
    f>>m;
    while(m--)
    {
        int tip, x;
        f>>tip>>x;
        if(tip == 0)
        {
            int l = 1, r = n, mij, pozMax = -1;
            while(l<=r)
            {
                mij = (l+r)/2;
                if(v[mij] == x)
                {
                    pozMax = mij;
                    l = mij + 1;
                }
                else if(v[mij] < x)
                {
                    l = mij + 1;
                }
                else
                {
                    r = mij - 1;
                }
            }
            g<<pozMax<<'\n';
        }
        else if(tip == 1)
        {
            int l = 1, r = n, mij, pozMax;
            while(l<=r)
            {
                mij = (l+r)/2;
                if(v[mij] <= x)
                {
                    l = mij + 1;
                    pozMax = mij;
                }
                else
                {
                    r = mij - 1;
                }
            }
            g<<pozMax<<'\n';
        }
        else
        {
            int l=1,r=n,mij, pozMin;
            while(l<=r)
            {
                mij = (l+r)/2;
                if(v[mij] >= x)
                {
                    r = mij - 1;
                    pozMin = mij;
                }
                else
                {
                    l = mij + 1;
                }
            }
            g<<pozMin<<'\n';
        }
    }
    return 0;
}