P15595 [ICPC 2020 Jakarta R] Shopping Changes

菲利克斯和他的 $M$ 个朋友今天正在疯狂购物。最近的一次现金交易中，他收到了由 $N$ 张钞票组成的找零。菲利克斯想把他收到的钞票按原顺序塞进自己的钱包。 例如，假设菲利克斯收到的找零有 $N = 4$ 张钞票，顺序为 $C_1\ C_2\ C_3\ C_4$。假设菲利克斯钱包中已有 $3$ 张钞票，顺序为 $W_1\ W_2\ W_3$，那么有四种方式将找零塞入他的钱包。 1. 将找零塞在第 $1$ 张钞票之前。塞入后，钱包中的钞票顺序为：$C_1\ C_2\ C_3\ C_4\ W_1\ W_2\ W_3$。 2. 将找零塞在第 $1$ 张和第 $2$ 张钞票之间。塞入后，钱包中的钞票顺序为：$W_1\ C_1\ C_2\ C_3\ C_4\ W_2\ W_3$。 3. 将找零塞在第 $2$ 张和第 $3$ 张钞票之间。塞入后，钱包中的钞票顺序为：$W_1\ W_2\ C_1\ C_2\ C_3\ C_4\ W_3$。 4. 将找零塞在第 $3$ 张钞票之后。塞入后，钱包中的钞票顺序为：$W_1\ W_2\ W_3\ C_1\ C_2\ C_3\ C_4$。 菲利克斯是个整洁的人，他希望钱包里的钞票尽可能有序。因此，他想以一种使得塞入后钱包的 **逆序对数** 最小的方式塞入找零。钱包的 **逆序对数** 定义为钱包中满足以下条件的钞票对 $(x, y)$ 的数量： - 钞票 $x$ 比钞票 $y$ 更靠近前端，且 - 钞票 $x$ 的面值严格大于钞票 $y$ 的面值。 今天他感觉有点慷慨，不想自己留着找零，而是想把它送给其中一个朋友，并将找零塞入他们的钱包。第 $i$ 个朋友的钱包中有 $L_i$ 张钞票，其面值从前到后依次为 $W_i[1], W_i[2], \dots, W_i[L_i]$。菲利克斯想把找零送给能使得塞入后其钱包逆序对数最小的朋友。因此，对于他的每个朋友，菲利克斯需要计算如果将找零塞入他们的钱包，所能得到的最小逆序对数。

输入第一行包含两个整数 $N$ 和 $M$（$1 \leq N, M \leq 100\,000$），分别表示找零中钞票的数量和菲利克斯的朋友数量。接下来一行包含 $N$ 个整数 $C_i$（$1 \leq C_i \leq 10^9$），表示找零中每张钞票的面值。接下来 $M$ 行，每行以一个整数 $L_i$（$1 \leq L_i \leq 200\,000$）开头，表示第 $i$ 个朋友钱包中钞票的数量，后面跟着 $L_i$ 个整数 $W_i[j]$（$1 \leq W_i[j] \leq 10^9$），表示钱包中钞票的面值。所有 $L_i$ 之和不超过 $200\,000$。

对于每个朋友，按照输入顺序，输出一行一个整数，表示如果将找零塞入他们的钱包，所能得到的最小逆序对数。

#### 样例 #1 解释 对于第 $1$ 个朋友，将找零塞在第 $3$ 张和第 $4$ 张钞票之间，钱包中的钞票顺序为：$2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10$。因此，钱包的逆序对数为 $0$。 对于第 $2$ 个朋友，将找零塞在第 $1$ 张钞票之前，钱包中的钞票顺序为：$5\ 6\ 7\ 100\ 99$。因此，钱包的逆序对数为 $1$。无法得到更小的逆序对数。 对于第 $3$ 个朋友，将找零塞在第 $1$ 张和第 $2$ 张钞票之间，或第 $2$ 张和第 $3$ 张钞票之间，钱包的逆序对数为 $1$。无法得到更小的逆序对数。 翻译由 DeepSeek 完成