题目描述

给出一组整数，它的前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

样例解释

样例输入的数组为[1, 3, 1, 7, 2, 4]，共有3个询问：

1. 询问xi=3：前3个数是1、3、1，其中最大值为3，最小值为1，差值为3-1=2；
2. 询问xi=2：前2个数是1、3，其中最大值为3，最小值为1，差值为3-1=2；
3. 询问xi=6：前6个数是1、3、1、7、2、4，其中最大值为7，最小值为1，差值为7-1=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。