#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) { j = upper_bound(v + 1, v + n + 1,x) -v - 1;
            if (j <= n && j >= 1 && v[j] == x)
                printf("%d\n", j);
            else
                printf("-1\n");

							   }
					  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;
}