#include <iostream>
#include <fstream>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");



int main()
{

    int N;
    int M;
    int v[100000];

    in>>N;

    for(int i=1; i<=N; i++)
    {
        in>>v[i];
    }

    in>>M;

    int a, b;

    for(int i=0; i<M; i++)
    {
        in>>a>>b;

         int pas = 1<<17;
         int r = 0;

        if(a == 0)
        {

            while(pas)
            {
                if( pas+r <= N && v[pas+r] <= b)
                {
                    r+=pas;

                }

                pas/=2;

            }

            if(v[r] == b)
                out<<r;
            else
                out<<-1;
        }
        else if( a == 1 )
        {

            while(pas)
            {
                if( pas+r <= N && v[pas+r] <= b)
                {
                    r+=pas;

                }

                pas/=2;

            }


                out<<r;

        }

        else if( a == 2 )
        {
            r = N;



            while(pas)
            {


                if( r-pas > 0 && v[r-pas] >= b)
                {
                        r-=pas;
                }


                pas/=2;

            }

            out<<r;


        }

        out<<'\n';

    }



    return 0;
}