题目描述

给出一组整数，它的前 $x$ 个数称为它的前缀。前缀最值差指的是：数组前 $x$ 个数中最大值和最小值的差。现在有 $q$ 个询问，要求算出每个询问对应的前缀最值差。

输入格式

第一行一个正整数 $N$，表示数组元素的个数。
第二行 $N$ 个正整数 $a_i$，表示数组元素。
第三行一个正整数 $q$，表示询问个数。
第四行 $q$ 个正整数 $x_i$，分别表示要求的前缀长度。

输出格式

一行，输出每个询问的答案（前缀最值差），用空格分隔。

样例

6
1 3 1 7 2 4
3
3 2 6

2 2 6

样例解释
数组为 $[1, 3, 1, 7, 2, 4]$，共 $3$ 个询问：

• $x_1=3$：前 $3$ 个数 $[1,3,1]$，最大值 $3$，最小值 $1$，差值为 $2$；
• $x_2=2$：前 $2$ 个数 $[1,3]$，最大值 $3$，最小值 $1$，差值为 $2$；
• $x_3=6$：前 $6$ 个数 $[1,3,1,7,2,4]$，最大值 $7$，最小值 $1$，差值为 $6$。
  输出结果为 2 2 6。

数据范围

• 对于 $50\%$ 的数据：$1 \le N \le 1000$，$q \le 1000$，$a_i < 1000$，$1 \le x_i \le N$；
• 对于 $100\%$ 的数据：$1 \le N \le 10^6$，$q \le 10^6$，$a_i < 10^9$，$1 \le x_i \le N$。