Felix 和他的 $M$ 个朋友今天疯狂购物。在最近的一次现金交易中，他收到了 $N$ 张钞票作为找零。Felix 想把这些收到的钞票塞进他的钱包里，且不能改变它们的顺序。

例如，假设 Felix 收到的找零有 $N = 4$ 张钞票，顺序为 $C_1, C_2, C_3, C_4$。假设 Felix 的钱包里原有 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$。

作为一个爱整洁的人，Felix 希望钱包里的钞票尽可能有序。因此，他想以一种能使塞入找零后钱包的逆序对数量最小化的方式进行操作。钱包的逆序对数量是指钱包中满足以下条件的钞票对 $(x, y)$ 的数量：

• 钞票 $x$ 比钞票 $y$ 更靠前，且
• 钞票 $x$ 的面值严格大于钞票 $y$ 的面值。

今天 Felix 很大方，他不想保留这些找零，而是想把它们送给其中一位朋友，并把找零塞进他们的钱包里。第 $i$ 位朋友的钱包里有 $L_i$ 张钞票，其面值分别为 $W_i[1], W_i[2], \dots, W_i[L_i]$（从最靠前到最靠后）。Felix 想把找零送给能使塞入找零后钱包逆序对数量最小化的那位朋友。因此，对于每一位朋友，Felix 需要计算如果他将找零塞入该朋友的钱包，其钱包能达到的最小逆序对数量。

输入格式

输入第一行包含两个整数：$N$ 和 $M$ ($1 \le N, M \le 100\,000$)，分别表示找零中的钞票数量和 Felix 的朋友数量。下一行包含 $N$ 个整数：$C_i$ ($1 \le C_i \le 10^9$)，表示找零中钞票的面值。接下来的 $M$ 行，每行首先给出一个整数 $L_i$ ($1 \le L_i \le 200\,000$)，表示第 $i$ 位朋友钱包中的钞票数量，随后是 $L_i$ 个整数：$W_i[j]$ ($1 \le W_i[j] \le 10^9$)，表示钱包中钞票的面值。所有 $L_i$ 之和不超过 $200\,000$。

输出格式

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

样例

样例输入 1

3 3
5 6 7
6 2 3 4 8 9 10
2 100 99
3 5 6 7

样例输出 1

0
1
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$。没有办法达到更小的逆序对数量。

样例输入 2

3 2
7 6 5
6 2 3 4 8 9 10
6 10 9 8 4 3 2

样例输出 2

3
27