设 $p_1, \dots, p_n$ 是 $[1, \dots, n]$ 的一个排列。

设 $p$ 的 $q$-子序列为 $[1, q]$ 的一个排列，其元素的相对顺序与在 $p_1, \dots, 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}$。

对于每个满足 $1 \le q \le n$ 的 $q$，设 $a_1, \dots, a_q$ 为 $p$ 的 $q$-子序列。对于每个满足 $1 \le i \le q$ 的 $i$，按照上述定义计算 $pre(i)$ 和 $nxt(i)$。然后，你将获得若干个整数 $x$，对于其中的每一个，你都需要计算 $\sum_{i=1}^q \min(nxt(i) - pre(i), x)$。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 3 \cdot 10^5$) —— 排列的长度。

第二行包含 $n$ 个整数 $p_1, \dots, p_n$ ($1 \le p_i \le n$) —— 初始排列。

接下来，对于按升序排列的每个满足 $1 \le q \le n$ 的 $q$，你将获得一个整数 $k$ ($0 \le k \le 10^5$)，表示针对 $q$-子序列的询问次数。随后的一行包含 $k$ 个数字：每个数字代表单次询问中 $x$ 的值 ($1 \le x \le 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$。