令 $$$p_1, \ldots, p_n$$$ 为 $$$[1, \ldots, n]$$$ 的排列。
令 $$$p$$$ 的 $$$q$$$ 子序列为 $$$[1, q]$$$ 的排列,其元素的相对顺序与 $$$p_1, \ldots, p_n$$$ 中的相对顺序相同。也就是说,我们按照原始顺序从$$$p$$$中一起提取不超过$$$q$$$的所有元素,它们构成$$$p$$$的$$$q$$$子序列。
对于给定数组 $$$a$$$,令 $$$pre(i)$$$ 为满足 $$$pre(i) < i$$$ 且 $$$a_{pre(i)} > a_i$$$ 的最大值。如果不存在,则令 $$$pre(i) = -10^{100}$$$。令 $$$nxt(i)$$$ 为满足 $$$nxt(i) > i$$$ 且 $$$a_{nxt(i)} > a_i$$$ 的最小值。如果不存在,则令 $$$nxt(i) = 10^{100}$$$。
对于每个 $$$q$$$ 使得 $$$1 \leq q \leq n$$$,令 $$$a_1, \ldots, a_q$$$ 为 $$$p$$$ 的 $$$q$$$ 子序列。对于每个 $$$i$$$,$$$1 \leq i \leq q$$$、$$$pre(i)$$$ 和 $$$nxt(i)$$$ 将按照定义进行计算。然后,您将获得一些整数值 $$$x$$$,并且对于每个整数值,您必须计算 $$$\sum\limits_{i=1}^q \min(nxt(i) - pre(i), x)$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\le t\le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3\cdot 10^5$$$) — 排列的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) - 初始排列。
然后,对于每个 $$$q$$$ ,使得 $$$1 \leq q \leq n$$$ 按升序排列,您将获得一个整数 $$$k$$$ ($$$0 \leq k \leq 10^5$$$),表示 $$$q$$$ 子序列的查询数量。然后一行中的 $$$k$$$ 数字如下:每个数字都是单个查询的 $$$x$$$ 的值 ($$$1 \leq x \leq q$$$)。
保证所有测试用例的$$$n$$$总和不超过$$$3\cdot 10^5$$$,并且所有测试用例的$$$k$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,对于每个查询,打印一行带有整数:查询的答案。
示例
输入 #1
1 7 6 1 4 3 2 5 7 1 1 0 1 3 1 2 3 1 2 3 1 3 2 2 6
输出 #1
1 9 8 5 10 14 16 14 30
注意
$$$1$$$子序列是$$$[1]$$$,并且$$$pre=[-10^{100}]$$$、$$$nxt=[10^{100}]$$$。 $$$ans(1)=\min(10^{100}-(-10^{100}),1)=1$$$。
$$$5$$$子序列是$$$[1,4,3,2,5]$$$,并且$$$pre=[-10^{100},-10^{100},2,3,-10^{100}]$$$,$$$nxt=[2,5,5,5,10^{100}]$$$。 $$$ans(1)=5,ans(2)=10,ans(3)=14$$$。