说明

给出一组整数，它的前x个数称为它的前缀，前缀最值差指的是：数组前x个数中最大值和最小值的差，这个问题到也难不倒小明。

但现在有q个问题询问，要求算出每个问题的前缀最值差。这样工作量就太大了。你有什么办法吗？

输入格式

   第一行有一个正整数N，表示给出的这组正整数的个数。

   第二行有N个正整数ai 。

   第三行有一个正整数q,表示有q个询问。

   第四行有q个正整数xi，分别表示要求前xi个数中最大值和最小值的差。

输出格式

 输出，每个询问的答案。

样例

6
1 3 1 7 2 4 
3
3 2 6

2 2 6

提示

【数据范围】

  50%数据, 1<= N<=1000, q<=1000, ai<1000,1<=xi<=N;

100%数据, 1<= N<=1000000, q<=1000000, ai<1000000000,1<=xi<=N; 

此题需要使用scanf和printf。

int n;

cin>>n;等于scanf("%d",&n);

cout<<n;等于printf("%d",n);