F.前驱与后继 Next and Prev

时间限制：$15$ 秒 内存限制：$1024$ 兆字节

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

定义 $p$ 的 $q$-子序列 是 $[1,q]$ 的一个排列，它的元素在 $p_1,\dots,p_n$ 中的相对顺序保持不变。 也就是说，从 $p$ 中提取所有不超过 $q$ 的元素，保持原有顺序，得到的序列就是 $p$ 的 $q$-子序列。

对于一个数组 $a$，定义：

• $\boldsymbol{pre(i)}$：满足 $pre(i) < i$ 且 $a_{pre(i)} > a_i$ 的最大下标；若不存在，令 $pre(i) = -10^{100}$。
• $\boldsymbol{nxt(i)}$：满足 $nxt(i) > i$ 且 $a_{nxt(i)} > a_i$ 的最小下标；若不存在，令 $nxt(i) = 10^{100}$。

对于每个 $q$（满足 $1 \le q \le n$），设 $a_1,\dots,a_q$ 是 $p$ 的 $q$-子序列。 按照定义计算每个位置 $i$ 的 $pre(i)$ 和 $nxt(i)$。

给定若干个询问值 $x$，对每个 $x$ 计算：

输入格式

输入包含多组测试数据。 第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。

每组测试数据格式如下：

1. 第一行一个整数 $n$（$1 \le n \le 3 \times 10^5$），表示排列长度。
2. 第二行 $n$ 个整数 $p_1,\dots,p_n$（$1 \le p_i \le n$），表示初始排列。
3. 接下来按 $q=1$ 到 $q=n$ 的顺序，依次给出每个 $q$ 对应的询问：
   • 一个整数 $k$（$0 \le k \le 10^5$），表示该 $q$ 的询问数量。
   • 一行 $k$ 个整数 $x$（$1 \le x \le q$），表示每个询问的参数。

保证：

• 所有测试数据的 $n$ 之和 $\le 3 \times 10^5$；
• 所有测试数据的 $k$ 之和 $\le 10^5$。

输出格式

对每个询问，输出一行一个整数，表示答案。

样例输入

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
9
8
5
10
14
16
14
30

样例解释

• $q=1$ 时，$q$-子序列为 $[1]$，$pre = [-10^{100}]$，$nxt = [10^{100}]$。 答案：$\min(10^{100}-(-10^{100}),\ 1) = 1$。

• $q=5$ 时，$q$-子序列为 $[1,4,3,2,5]$。 $pre = [-10^{100},-10^{100},2,3,-10^{100}]$ $nxt = [2,5,5,5,10^{100}]$ 询问 $x=1$ 答案为 $5$，$x=2$ 答案为 $10$，$x=3$ 答案为 $14$。