#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int n,v[100000],m,a[5];
ofstream out("cautbin.out");
int i,li,ls,mij,gasit;

void bin (int i,int j,int x)
{
    int maxpoz=0;
    li=i;
    ls=j;
    gasit=0;
    while(li<=ls)
    {
       
        mij=floor((li+ls)/2); //aflam indicele care reprezinta mijlocul tabloului.
        
        if(x==v[mij])
        {
            if(maxpoz<mij)
                maxpoz=mij;
            gasit=1;
            li=mij+1;
        }
        
        else if(x>v[mij])
            li=mij+1;
        else ls=mij-1;
    }
    if(gasit==0)
        out<<-1<<endl;
    else
        out<<maxpoz<<endl;
}
void bin1(int i,int j,int x)
{
    int maxpoz1=0;
    li=i;
    ls=j;
    gasit=0;
    while(li<=ls)
    {
        
        mij=floor((li+ls)/2); //aflam indicele care reprezinta mijlocul tabloului.
        
        if(v[mij]<=x)
        {
            if(maxpoz1<mij)
                maxpoz1=mij;
            gasit=1;
            li=mij+1;
        }
        
        else if(x>v[mij])
            li=mij+1;
        else ls=mij-1;
    }
    
        out<<maxpoz1<<endl;
    
        }
void bin2(int i,int j,int x)
{
    int minpoz2=200000;
    li=i;
    ls=j;
    gasit=0;
    while(li<=ls)
    {
        
        mij=floor((li+ls)/2); //aflam indicele care reprezinta mijlocul tabloului.
        
        if(v[mij]>=x)
        {
            if(minpoz2>mij)
                minpoz2=mij;
            gasit=1;
            ls=mij-1;
        }
        
        else if(x>v[mij])
            li=mij+1;
        else ls=mij-1;
    }
        out<<minpoz2<<endl;
    
}

int main()
{
    
    ifstream in("cautbin.in");
    in>>n;
    //cout<<n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    for(int i=1;i<=m;i++){
    for(int j=1;j<=2;j++)
        in>>a[j];
    if(a[1]==0)
        bin(1,n,a[2]);
    if(a[1]==1)
        bin1(1,n,a[2]);
    if(a[1]==2)
        bin2(1,n,a[2]);
    }
}