Migrated from Lutece 2682 水の杯の杯

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

我们都知道，军训是很累的。所以现在有 $n$ 名同学想要喝水，他们的水杯在地上摆成了一排，同学和杯子都从 $1$ 到 $n$ 编号，并且每个同学只能喝自己杯子里的水（也就是编号为 $i$ 的同学只能喝编号为 $i$ 的水杯中的水）。

我们都知道，水杯里是有水的。所以每个杯子里有 $a_i$ 单位的水。

我们都知道，教官想要同学们都整整齐齐的。所以在 $n$ 名同学喝水后（可以不喝），$n$ 个杯子中水的量必须单调不降。

我们都知道，同学们的体能是各不相同的。所以我们要求出指定的 $m$ 名同学 $b_1,b_2,\ldots,b_m$ 的喝水量的最小值。

Input

第一行一个正整数 $n\ (1\le n\le 3\times 10^5)$，表示水杯数量。

第二行 $n$ 个正整数 $a_i\ (1\le a_i\le 10^9)$，表示水杯中水的量。

第三行一个正整数 $m\ (1\le m\le n)$，表示指定的同学数量。

第四行 $m$ 个正整数 $b_i\ (1\le b_i\le n)$，表示指定的同学的编号，保证 $\forall i\in[1,n),b_i<b_{i+1}$。

Output

输出 $m$ 行，每行输出一个整数，第 $i$ 行输出 $b_i$ 同学的喝水量的最小值。

Samples

5
1 5 3 2 6
1
3

1

Note

由于 I/O 量较大，请使用 Java 和 Python 的选手选择尽可能快的 I/O 方式。

Resources

电子科技大学第十二届 ACM 趣味程序设计竞赛