#include <iostream>
#include <fstream>


using namespace std;

int v[100100];
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int caut(int st,int dr,int x){
int mij;
if(st<=dr){
mij=st+(dr-st)/2;
if(v[mij]==x){
while(v[mij+1]==v[mij])mij++;
return mij;
}
else if(v[mij]>x)caut(mij+1,dr,x);
else caut(st,mij-1,x);
}
return -1;
}

int lower_bin(int st, int dr, int x){
int mij;
while(st<dr){
mij=st+(dr-st)/2;
if(v[mij]>x)dr=mij-1;
else if(v[mij]<x)st=mij+1;
else if(v[mij]==x)break;
}
if(v[mij]==x){
while(v[mij+1]==v[mij])mij++;
}
else if(v[mij]>x)mij--;
return mij;
}

int upper_bin(int st, int dr, int x){
int mij;
while(st<dr){
mij=st+(dr-st)/2;
if(v[mij]>x)dr=mij-1;
else if(v[mij]<x)st=mij+1;
else if(v[mij]==x)break;
}
if(v[mij]==x){
while(v[mij-1]==v[mij])mij--;
}
else if(v[mij]<x)mij++;
return mij;
}

int main()
{int n;
int op,arg;
in>>n;
for(int i=1;i<=n;i++)in>>v[i];
int nrop;
in>>nrop;
for(int i=1;i<=nrop;i++){
in>>op>>arg;
switch(op){
case 0:{
out<<caut(1,n,arg);
break;
}
case 1:{
out<<lower_bin(1,n,arg);
break;
}
case 2:{
out<<upper_bin(1,n,arg);
break;
}

}

out<<'\n';
}

    return 0;
}