CF1841E Fill the Matrix

有一个方阵，由 $n$ 行 $n$ 列的格子组成，行和列都从 $1$ 到 $n$ 编号。每个格子被涂成黑色或白色。在第 $i$ 列中，从第 $1$ 行到第 $a_i$ 行的格子是黑色的，从第 $a_i+1$ 行到第 $n$ 行的格子是白色的。 你需要在矩阵中放入 $m$ 个整数，分别为 $1$ 到 $m$。有以下两个规则： - 每个格子最多只能放一个整数； - 黑色格子不能放整数。 矩阵的美丽值定义为：有多少个 $j$ 满足 $j+1$ 被放在与 $j$ 同一行、相邻的右侧列（即右边相邻的格子）。 请问，矩阵的最大美丽值是多少？

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示矩阵的大小。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le n$），表示每一列中黑色格子的数量。 第三行包含一个整数 $m$（$0 \le m \le \sum\limits_{i=1}^n n - a_i$），表示你需要在矩阵中放入的整数数量。注意，这个数可能无法用 32 位整数类型存储。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示在放入所有 $m$ 个整数后，矩阵的最大美丽值。保证白色格子的数量不少于 $m$，即一定有解。

由 ChatGPT 4.1 翻译