#include <fstream>

using namespace std;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
long long n,m,x[100005],i,j,aux,a,b,st,dr,sw=0,mid;
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>x[i];
        fin>>m;
    for(j=1;j<=m;j++)
    {
        fin>>b>>a;
        if(b==0)
        {
            st=1;
            dr=n;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(x[mid]==a)
                    break;
                if(x[mid]<a)
                    st=mid+1;
                else
                    dr=mid-1;
            }
            if(st<=dr)
            {
                while(x[mid]==a)
                    mid++;
                fout<<mid-1<<endl;
            }
            else
                fout<<-1;
        }
        if(b==1)
        {
             st=1;
            dr=n;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(x[mid]<=a)
                    break;
                if(x[mid]>a)
                    dr=mid-1;
                    else
                        st=mid+1;
            }

           while(x[mid]<=a && mid<=n)
                    mid++;
                fout<<mid-1<<endl;
        }
        if(b==2)
        {
            st=1;
            dr=n;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(x[mid]>=a)
                    break;
                if(x[mid]<a)
                    st=mid+1;
                else
                    dr=mid-1;
            }
                while(x[mid]>=a)
                    mid--;
                fout<<mid+1<<endl;
        }
    }
    return 0;
}