311300: CF1967F. Next and Prev

F. Next and Prevtime limit per test15 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

Let $p_1, \ldots, p_n$ be a permutation of $[1, \ldots, n]$.

Let the $q$-subsequence of $p$ be a permutation of $[1, q]$, whose elements are in the same relative order as in $p_1, \ldots, p_n$. That is, we extract all elements not exceeding $q$ together from $p$ in the original order, and they make the $q$-subsequence of $p$.

For a given array $a$, let $pre(i)$ be the largest value satisfying $pre(i) < i$ and $a_{pre(i)} > a_i$. If it does not exist, let $pre(i) = -10^{100}$. Let $nxt(i)$ be the smallest value satisfying $nxt(i) > i$ and $a_{nxt(i)} > a_i$. If it does not exist, let $nxt(i) = 10^{100}$.

For each $q$ such that $1 \leq q \leq n$, let $a_1, \ldots, a_q$ be the $q$-subsequence of $p$. For each $i$ such that $1 \leq i \leq q$, $pre(i)$ and $nxt(i)$ will be calculated as defined. Then, you will be given some integer values of $x$, and for each of them you have to calculate $\sum\limits_{i=1}^q \min(nxt(i) - pre(i), x)$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 3\cdot 10^5$) — the length of the permutation.

The second line of each test case contains $n$ integers $p_1, \ldots, p_n$ ($1 \leq p_i \leq n$) — the initial permutation.

Then, for each $q$ such that $1 \leq q \leq n$ in ascending order, you will be given an integer $k$ ($0 \leq k \leq 10^5$), representing the number of queries for the $q$-subsequence. Then $k$ numbers in a line follow: each of them is the value of $x$ for a single query ($1 \leq x \leq q$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10^5$ and the sum of $k$ over all test cases does not exceed $10^5$.

Output

For each test case, for each query, print a single line with an integer: the answer to the query.

ExampleInput

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

Output

1
9
8
5
10
14
16
14
30

Note

The $1$-subsequence is $[1]$, and $pre=[-10^{100}]$, $nxt=[10^{100}]$. $ans(1)=\min(10^{100}-(-10^{100}),1)=1$.

The $5$-subsequence is $[1,4,3,2,5]$, and $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$.

题目大意：
给定一个长度为n的排列p_1, ..., p_n，排列的元素为[1, ..., n]。定义p的q子序列为[1, q]的一个排列，其元素在p_1, ..., 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 ≤ q ≤ n，设a_1, ..., a_q为p的q子序列。对于每个1 ≤ i ≤ q，根据定义计算pre(i)和nxt(i)。然后，给出一些整数x的值，对于每个x计算Σ(min(nxt(i) - pre(i), x))。

输入输出数据格式：
每个测试包含多个测试用例。第一行包含测试用例数t（1 ≤ t ≤ 10^4）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 3×10^5）——排列的长度。

每个测试用例的第二行包含n个整数p_1, ..., p_n（1 ≤ p_i ≤ n）——初始排列。

然后，按升序对于每个1 ≤ q ≤ n，给出一个整数k（0 ≤ k ≤ 10^5），表示对q子序列的查询数。接下来一行包含k个数：每个数是单个查询的x值（1 ≤ x ≤ q）。

保证所有测试用例的n之和不超过3×10^5，k之和不超过10^5。

对于每个测试用例，对于每个查询，输出一行，包含一个整数：查询的答案。题目大意： 给定一个长度为n的排列p_1, ..., p_n，排列的元素为[1, ..., n]。定义p的q子序列为[1, q]的一个排列，其元素在p_1, ..., 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 ≤ q ≤ n，设a_1, ..., a_q为p的q子序列。对于每个1 ≤ i ≤ q，根据定义计算pre(i)和nxt(i)。然后，给出一些整数x的值，对于每个x计算Σ(min(nxt(i) - pre(i), x))。 输入输出数据格式： 每个测试包含多个测试用例。第一行包含测试用例数t（1 ≤ t ≤ 10^4）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 3×10^5）——排列的长度。 每个测试用例的第二行包含n个整数p_1, ..., p_n（1 ≤ p_i ≤ n）——初始排列。 然后，按升序对于每个1 ≤ q ≤ n，给出一个整数k（0 ≤ k ≤ 10^5），表示对q子序列的查询数。接下来一行包含k个数：每个数是单个查询的x值（1 ≤ x ≤ q）。 保证所有测试用例的n之和不超过3×10^5，k之和不超过10^5。 对于每个测试用例，对于每个查询，输出一行，包含一个整数：查询的答案。