← 返回题目列表

Codeforces · 1061/B

B. 意见很重要

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

您来到展会,一件展品引起了您的注意。它由 $$$n$$$ 块堆叠组成,其中第 $$$i$$$ 堆叠由位于表面的 $$$a_i$$$ 块组成。

展品的高度等于$$$m$$$。因此,每个堆栈中的块数小于或等于 $$$m$$$。

天花板上有一个摄像头,可以看到积木的俯视图,右侧墙上有一个摄像头,可以看到积木的侧视图。

找到可以删除的最大块数,这样两个摄像机的视图都不会改变。

请注意,虽然最初所有块都堆叠在地板上,但在移除某些块后,它们不需要保持与地板的连接。整个展览没有重力,所以即使把下面的方块移开,也不会掉落任何方块。也不允许用手移动方块。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le m \le 10^9$$$) — 堆叠的数量和展品的高度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) - 每个堆栈中从左到右的块数。

输出

精确打印一个整数——可以删除的最大块数。

示例

输入 #1

5 6
3 3 3 3 3

输出 #1

10

输入 #2

3 5
1 2 4

输出 #2

3

输入 #3

5 5
2 3 1 4 4

输出 #3

9

输入#4

1 1000
548

输出#4

0

输入 #5

3 3
3 1 1

输出 #5

1

注意

下图说明了第一个示例及其可能的解决方案。

蓝色单元格表示已删除的块。有 $$$10$$$ 蓝色单元格,所以答案是 $$$10$$$。