#include <stdio.h>
unsigned int n,m;
unsigned int a[100002];

unsigned int ln(unsigned int x){
unsigned int lo=1,hi=n,mid;

while (lo<=hi){
mid=lo+(hi-lo)/2;
if((a[mid]==x)&&((x<a[mid+1])||(mid==n))){return mid;}else
{if(a[mid]==x){lo=mid+1;}else{if(a[mid]<x){lo=mid+1;}else{hi=mid-1;}}}

}
return -1;
}

unsigned int egyes(unsigned int x){
unsigned int lo=1,hi=n,mid;
while(lo<=hi){
mid=lo+(hi-lo)/2;

if((a[mid]<=x)&&((x<a[mid+1])||(mid==n))){return mid;}else
{if(a[mid]==x){lo=mid+1;}else{if(a[mid]<x){lo=mid+1;}else{hi=mid-1;}}}

}

}



unsigned int kettes(unsigned int x){
unsigned int lo=1,hi=n,mid;
while(lo<=hi){
mid=lo+(hi-lo)/2;

if((a[mid]>=x)&&((x>a[mid-1])||(mid==1))){return mid;}else
{if(a[mid]==x){hi=hi-1;}else{if(a[mid]<x){lo=mid+1;}else{hi=mid-1;}}}

}

}

int main(){
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);

unsigned int i,temp1,temp2;

scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%d",&a[i]);

}

scanf("%d",&m);
for (i=1;i<=m;i++){
scanf("%d %d",&temp1,&temp2);

switch(temp1){

case 0:
	printf("%d\n",ln(temp2));
	break;
case 1:
	printf("%d\n",egyes(temp2));
	break;
case 2:
	printf("%d\n",kettes(temp2));
	break;
}

}

return 0;
}