题目描述

给定 $N$ 个正整数，每次询问给出 $x$，求前 $x$ 个数中的最大值与最小值之差。

输入格式

第一行 $N$；第二行 $N$ 个整数；第三行 $q$；第四行 $q$ 个询问位置。

输出格式

按顺序输出所有询问的答案。

样例

6
1 3 1 7 2 4
3
3 2 6

2 2 6

数据范围

50%的数据：$N,q\le1000$，$a_i<1000$。

100%的数据：$1\le N,q\le10^6$，$1\le a_i<10^9$，$1\le x_i\le N$。