#include<iostream>

#include<fstream>

using namespace std;



ifstream f("cautbin.in");

ofstream g("cautbin.out");



int n,v[100001],x,m,k,st,dr,mij,sol;



int main()

{

    f>>n;

    for(int i=1;i<=n;i++)

        f>>v[i];

    f>>m;

    for( ; m; m--)

    {

        f>>k>>x;

        st=1;

        dr=n;

        sol=-1;

        if(k==0)

        {

            while(st<=dr)

            {

                mij=(st+dr)/2;

                if(v[mij]==x)

                {

                    sol=mij;

                    st=mij+1;

                }

                else

                    if(v[mij]<x)

                        st=mij+1;

                    else

                        dr=mij-1;

            }

            g<<sol<<'\n';

        }

        else

            if(k==1)

            {

                while(st<=dr)

                {

                    mij=(st+dr)/2;

                    if(v[mij]<=x)

                    {

                        sol=mij;

                        st=mij+1;

                    }

                    else

                        dr=mij-1;

            }

            g<<sol<<'\n';

            }

            else

            {

                while(st<=dr)

                {

                    mij=(st+dr)/2;

                    if(v[mij]>=x)

                    {

                        sol=mij;

                        dr=mij-1;

                    }

                    else

                        st=mij+1;

                }

                g<<sol<<'\n';

            }

    }

    return 0;

}