CF2075C Two Colors

Monocarp 决定按照以下规则粉刷围栏： - 每块木板必须被涂上恰好一种颜色； - 使用的不同颜色总数必须恰好为两种； - 相同颜色的木板必须形成连续序列，即对于所有被涂成同一颜色的木板对，它们之间不存在被涂成其他颜色的木板。 Monocarp 有 $m$ 种不同的颜料，其中第 $i$ 种颜色的颜料最多可以涂 $a_i$ 块木板。Monocarp 不会购买额外颜料。 你的任务是计算满足 Monocarp 所有描述的愿望的围栏涂色方式数目。两种涂色方式被认为是不同的，当且仅当存在至少一块木板在这两种方式中被涂成不同颜色。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n, m \le 2 \cdot 10^5$）——围栏的木板数量以及 Monocarp 拥有的不同颜色数量。 第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$（$1 \le a_i \le n$），其中 $a_i$ 表示第 $i$ 种颜色最多可涂的木板数量。 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。所有测试用例的 $m$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出满足条件的不同涂色方式数目。

第一个测试案例中，存在 $4$ 种不同的涂色方式（木板从左到右的颜色编号序列如下）： 1. $[1, 2, 2, 2, 2]$； 2. $[1, 1, 2, 2, 2]$； 3. $[2, 2, 2, 1, 1]$； 4. $[2, 2, 2, 2, 1]$。 第二个测试案例中，存在 $6$ 种不同的涂色方式（木板从左到右的颜色编号序列如下）： 1. $[1, 2, 2, 2, 2]$； 2. $[1, 1, 2, 2, 2]$； 3. $[1, 1, 1, 2, 2]$； 4. $[2, 2, 1, 1, 1]$； 5. $[2, 2, 2, 1, 1]$； 6. $[2, 2, 2, 2, 1]$。 翻译由 DeepSeek R1 完成