#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream  g("cautbin.out");
int v[100005];
int main()
{
    int n,m,c,x,i,j,e,poz;
    f>>n;
    for (int i=1; i<=n; i++)
    {
        f>>v[i];
    }
    f>>m;
    for (int abc=1; abc<=m; abc++)
    {
        f>>c>>x;
        poz=-1;
        i=1;
        j=n;
        if (c==0)
        {

            while (i<=j)
            {
                e=(i+j)/2;
                if (v[e]==x and e>poz)
                {
                    poz=e;
                }
                if (v[e]<=x)
                {
                    i=e+1;
                }
                else
                {
                    j=e-1;
                }
            }
            if  (poz==-1)
            {
                g<<"-1"<<'\n';
            }else
            {
                g<<poz<<'\n';
            }
        }
        if (c==1)
        {
            while (i<=j)
            {
                e=(i+j)/2;
                if (v[e]<=x and e>poz)
                {
                    poz=e;
                }
                if (v[e]<=x)
                {
                    i=e+1;
                }
                else
                {
                    j=e-1;
                }
            }
            g<<poz<<'\n';
        }
        if(c==2)
        {
            poz=1000000;
            while (i<=j)
            {
                e=(i+j)/2;
                if (v[e]>=x and e<poz)
                {
                    poz=e;
                }
                if (v[e]<x)
                {
                    i=e+1;
                }
                else
                {
                    j=e-1;
                }
            }
             g<<poz<<'\n';
        }
    }
    return 0;
}