#include <iostream>
#include <fstream>
using namespace std;

int v[100001];

int main()
{
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");

    int n, i, c, x, m, p, u, mij;
    bool ok;

    fin>>n;

    for(i=1; i<=n; i++)
    {
        fin>>v[i];
    }

    fin>>m;

    for(i=1; i<=m; i++)
    {
        fin>>c>>x;

        if(c==0)
        {

            p=1;
            u=n;
            ok=0;

            while(p<=u && ok==0)
            {
                mij=(p+u)/2;

                if(v[mij]==x && v[mij+1] > x) ok=1;
                else if(v[mij] < x) p=mij+1;
                else if(v[mij]>x) u=mij-1;
                else if(v[mij+1] <= x) p=mij+1;
            }

            if(ok==0) fout<<-1<<"\n";
            else fout<<mij<<"\n";
        }

        else if(c==1)
        {
            p=1;
            u=n-1;
            ok=0;

            while(p<=u && ok==0)
            {
                mij=(p+u)/2;

                if(v[mij] <=x && v[mij+1] > x) ok=1;
                else if(v[mij]>x) u=mij-1;
                else if(v[mij+1]<=x) p=mij+1;
            }

            if(ok==0) fout<<n<<"\n";
            else fout<<mij<<"\n";
        }

        else if(c==2)
        {
            p=1;
            u=n;
            ok=0;

            while(p<=u && ok==0)
            {
                mij=(p+u)/2;

                if(v[mij] >=x && v[mij-1] < x) ok=1;
                else if(v[mij] < x) p=mij+1;
                else if(v[mij-1] >=x ) u=mij-1;
            }

            fout<<mij<<"\n";
        }
    }
}