using namespace std;
#include<fstream>
#define Nmax 100002
ifstream eu("cautbin.in");
ofstream tu("cautbin.out");
int V[Nmax];
int N,M,x,val;

int BS1(int s,int d)
{
	int m,sol=-1;
    while(s<=d)
    {
        m=(s+d)/2;
        if(V[m]<=val)
        {
            if(V[m]==val)
                sol=m;
            s=m+1;
        }
        else
            if(V[m]>val)
                d=m-1;
    }
    return sol;
}




int BS2(int s,int d)
{
    int m,sol=1;
    while(s<=d)
    {
        m=(s+d)/2;
        if(V[m]<=val)
        {
            sol=m;
            s=m+1;
        }
        else
            if(V[m]>=val)
            d=m-1;
    }
    return sol;
}



int BS3(int s,int d)
{
    int m,sol=1;
    while(s<=d)
    {
        m=(s+d)/2;
        if(V[m]>=val)
        {
            sol=m;
            d=m-1;
        }
        else
        if(V[m]<val)
            s=m+1;
    }
    return sol;
}

int main()
{
   eu>>N;
    for(int i=1;i<=N;i++)
        eu>>V[i];
    eu>>M;
    while(M--)
    {
        eu>>x>>val;
        if(x==0)
           tu<<BS1(1,N)<<"\n";
        if(x==1)
            tu<<BS2(1,N)<<"\n";
        if(x==2)
            tu<<BS3(1,N)<<"\n";
    }
    return 0;
}