6636: 前缀最值差
[Creator : ]
Description
老周给出一组整数，它的前 $x$ 个数称为它的前缀，前缀最值差指的是：数组前 $x$ 个数中最大值和最小值的差。
但现在有 $q$ 个问题询问，要求算出每个问题的前缀最值差。这样工作量就太大了。你有什么办法吗？
但现在有 $q$ 个问题询问，要求算出每个问题的前缀最值差。这样工作量就太大了。你有什么办法吗？
Input
第一行有一个正整数 $N$，表示给出的这组正整数的个数。
第二行有 $N$ 个正整数 $a_i$。
第三行有一个正整数 $q$，表示有 $q$ 个询问。
第四行有 $q$ 个正整数 $x_i$，分别表示要求前 $x_i$ 个数中最大值和最小值的差。
第二行有 $N$ 个正整数 $a_i$。
第三行有一个正整数 $q$，表示有 $q$ 个询问。
第四行有 $q$ 个正整数 $x_i$，分别表示要求前 $x_i$ 个数中最大值和最小值的差。
Output
一行包括 $q$ 个数，每个询问的答案。
Constraints
$50\%$ 数据，$1 \leq N \leq 1,000,\ 0 \leq q \leq 1,000, -1,000 < a_i <1,000,\ 1 \leq x_i \leq N$。
$100\%$ 数据，$1 \leq N \leq 1,000,000,\ q \leq 1,000,000,\ a_i<1,000,000,000,\ 1 \leq x_i \leq N$。
$100\%$ 数据，$1 \leq N \leq 1,000,000,\ q \leq 1,000,000,\ a_i<1,000,000,000,\ 1 \leq x_i \leq N$。
Sample 1 Input
6
1 3 1 7 2 4
3
3 2 6
Sample 1 Output
2 2 6