← 返回题目列表

Codeforces · 2075/C

C. 两种颜色

中文机器翻译题面 查看原题

Monocarp 在他的避暑别墅安装了新栅栏。栅栏由排成一排的相同尺寸的 $$$n$$$ 木板组成。

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$$$。

输出

对于每个测试用例,输出满足 Monocarp 所有描述的愿望的绘制栅栏的不同方法的数量。

示例

输入
复制

3
5 2
2 4
5 2
3 4
12 3
5 9 8

输出
复制

4
6
22

注意

在第一个测试用例中,有 $$$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]$$$.