#include<cstdio>
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) { j=0;st=1;dr=n;
									  while(st<dr&&!j) { mid=(st+dr)>>1;
														 if(v[mid]<=x&&v[mid+1]>=x)j=mid;
														 else if(v[mid]>x)dr=mid-1;
															  else st=mid+1;
														}
									  if(v[j]==x) { while(v[j]==x)j++; 
													printf("%d\n",j-1);
												  }
									  else printf("%d\n",j);
									}
					       else { j=0;st=1;dr=n;
									  while(st<dr&&!j) { mid=(st+dr)>>1;
														 if(v[mid]<=x&&v[mid+1]>=x)j=mid+1;
														 else if(v[mid]>x)dr=mid-1;
															  else st=mid+1;
														}
									  if(v[j]==x) { while(v[j]==x)j--; 
													printf("%d\n",j+1);
												  }
									  else printf("%d\n",j);
							    }
					}
  fclose(stdin);
  fclose(stdout);
  return 0;
}