← 返回题目列表

Codeforces · 1000/B

B. 点亮它

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

最近,您购买了一款全新的具有编程功能的智能灯。首先,您为灯设置了时间表。每天它都会在 $$$0$$$ 时刻打开电源,并在 $$$M$$$ 时刻关闭电源。此外,该灯允许您设置切换其状态的程序(状态为“灯亮”和“灯灭”)。不幸的是,一些程序已经安装到灯中。

该灯只允许播放好的节目。好的程序可以表示为非空数组 $$$a$$$,其中 $$$0 < a_1 < a_2 < \dots < a_{|a|} < M$$$。所有 $$$a_i$$$ 必须是整数。当然,预装的程序是一个好程序。

灯以下列方式遵循程序 $$$a$$$:在 $$$0$$$ 时刻打开电源并打开灯。然后在 $$$a_i$$$ 时刻,灯将其状态翻转到相反的状态(如果它被点亮,它就会关闭,反之亦然)。灯的状态会立即翻转:例如,如果您在 $$$1$$$ 时刻关灯,然后什么也不做,则灯点亮的总时间将为 $$$1$$$。最后,在 $$$M$$$ 时刻,无论其状态如何,灯都会关闭电源。

由于您不属于阅读说明的人,并且您不理解其编写的语言,因此您意识到(经过一些测试)更改预装程序的唯一可能方法。你最多可以在程序$$$a$$$中插入一个元素,所以修改后它仍然应该是一个好的程序。插入可以在 $$$a$$$ 的任意一对连续元素之间完成,甚至可以在 $$$a$$$ 的开头或结尾处完成。

找到一种方法来改变程序,使灯点亮的总时间尽可能长。也许你应该让程序保持不变。如果灯从$$$x$$$一直亮到$$$y$$$时刻,那么它会亮$$$y - x$$$时间单位。灯点亮的时间段被总结。

输入

第一行包含两个空格分隔的整数 $$$n$$$ 和 $$$M$$$ ($$$1 \le n \le 10^5$$$, $$$2 \le M \le 10^9$$$) — 程序 $$$a$$$ 的长度和电源关闭的时刻。

第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 < a_1 < a_2 < \dots < a_n < M$$$) — 最初安装的程序 $$$a$$$。

输出

打印唯一的整数 — 灯点亮时的最大可能总时间。

示例

输入 #1

3 10
4 6 7

输出 #1

8

输入 #2

2 12
1 10

输出 #2

9

输入 #3

2 7
3 4

输出 #3

6

注意

在第一个示例中,可能的最佳解决方案之一是在 $$$a_1$$$ 之前插入值 $$$x = 3$$$,因此程序将为 $$$[3, 4, 6, 7]$$$,灯点亮的时间等于 $$$(3 - 0) + (6 - 4) + (10 - 7) = 8$$$。其他可能的解决方案是在适当的位置插入 $$$x = 5$$$。

在第二个示例中,只有一个最佳解决方案:在 $$$a_1$$$ 和 $$$a_2$$$ 之间插入 $$$x = 2$$$。程序将变为$$$[1, 2, 10]$$$,答案将是$$$(1 - 0) + (10 - 2) = 9$$$。

在第三个示例中,最佳答案是保持程序不变,因此答案将为 $$$(3 - 0) + (7 - 4) = 6$$$。