#include<cstdio>
#include<algorithm>
using namespace std;
int n,v[100000],m,i,x,st,dr,mid,j;
int main()
{ freopen("cautbin.in","r",stdin);
  freopen("cautbin.out","w",stdout);
  scanf("%d",&n); 
  for(i=1;i<=n;i++) scanf("%d",&v[i]); 
  scanf("%d",&m);
  for(i=1;i<=m;i++) { scanf("%d%d",&j,&x);
	 				  if(j==0) { st=1;dr=n;
								 while(st<dr&&!j) { mid=(st+dr)>>1;
													if(v[mid]==x)j=mid;
												    else if(v[mid]>x)dr=mid-1;
														 else st=mid+1;
												  }
								 while(v[j]==x)j++;
								 printf("%d\n",j-1);
							   }
					  else if(j==1) { x=lower_bound(v+1,v+n+1,x+1)-v-1;
									  printf("%d\n",x);
									}
					       else { x=upper_bound(v+1,v+n+1,x-1)-v;
								  printf("%d\n",x);
							    }
					}
  fclose(stdin);
  fclose(stdout);
  return 0;
}