#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int N,M,i,st,dr,mij,pozMax;
unsigned int a[100001],q;
unsigned p;

int main()
{
    f>>N;
    for(i=1;i<=N;i++)
        f>>a[i];

    f>>M;
    for(i=1;i<=M;i++){
        f>>p>>q;

        if(p==0){
            st=1,dr=N;
            while(st<=dr){

                mij=(st+dr)/2;
                if(a[mij]>q)dr=mij-1;
                else st=mij+1;


            }

               mij=(st+dr)/2;
                if(a[mij]>q)mij--;

                if(a[mij]==q)g<<mij<<"\n";
                else g<<-1<<"\n";

        }else if(p==1){

            st=1,dr=N;
            while(st<dr){
                mij=(st+dr)/2;

            if(a[mij]>q)dr=mij;
            else st=mij+1;

            }

            mij=(dr+st)/2;
            if(a[mij]>q)
                --mij;

            g<<mij<<"\n";

        }else if(p==2){

            st=1,dr=N;
            while(st<dr){
                mij=(st+dr)/2;

                if(a[mij]<q)
                    st=mij+1;
                else
                    dr=mij;

            }

            mij=(st+dr)/2;
            if(a[mij]<q)
                ++ mij;

            g<<mij<<"\n";

        }

    }

}