English · Original
Chinese · Translation
Formal · Original
Recently, you bought a brand new smart lamp with programming features. At first, you set up a schedule to the lamp. Every day it will turn power on at moment $0$ and turn power off at moment $M$. Moreover, the lamp allows you to set a program of switching its state (states are "lights on" and "lights off"). Unfortunately, some program is already installed into the lamp.
The lamp allows only _good_ programs. Good program can be represented as a non-empty array $a$, where $0 < a_1 < a_2 < \dots < a_{|a|} < M$. All $a_i$ must be integers. Of course, preinstalled program is a good program.
The lamp follows program $a$ in next manner: at moment $0$ turns power and light on. Then at moment $a_i$ the lamp flips its state to opposite (if it was lit, it turns off, and vice versa). The state of the lamp flips instantly: for example, if you turn the light off at moment $1$ and then do nothing, the total time when the lamp is lit will be $1$. Finally, at moment $M$ the lamp is turning its power off regardless of its state.
Since you are not among those people who read instructions, and you don't understand the language it's written in, you realize (after some testing) the only possible way to alter the preinstalled program. You can **insert at most one** element into the program $a$, so it still should be a _good_ program after alteration. Insertion can be done between any pair of consecutive elements of $a$, or even at the begining or at the end of $a$.
Find such a way to alter the program that the total time when the lamp is lit is maximum possible. Maybe you should leave program untouched. If the lamp is lit from $x$ till moment $y$, then its lit for $y - x$ units of time. Segments of time when the lamp is lit are summed up.
## Input
First line contains two space separated integers $n$ and $M$ ($1 \le n \le 10^5$, $2 \le M \le 10^9$) — the length of program $a$ and the moment when power turns off.
Second line contains $n$ space separated integers $a_1, a_2, \dots, a_n$ ($0 < a_1 < a_2 < \dots < a_n < M$) — initially installed program $a$.
## Output
Print the only integer — maximum possible total time when the lamp is lit.
[samples]
## Note
In the first example, one of possible optimal solutions is to insert value $x = 3$ before $a_1$, so program will be $[3, 4, 6, 7]$ and time of lamp being lit equals $(3 - 0) + (6 - 4) + (10 - 7) = 8$. Other possible solution is to insert $x = 5$ in appropriate place.
In the second example, there is only one optimal solution: to insert $x = 2$ between $a_1$ and $a_2$. Program will become $[1, 2, 10]$, and answer will be $(1 - 0) + (10 - 2) = 9$.
In the third example, optimal answer is to leave program untouched, so answer will be $(3 - 0) + (7 - 4) = 6$.
最近，你购买了一盏具有编程功能的全新智能灯。最初，你为灯设置了计划：每天它会在时刻 $0$ 开启电源，在时刻 $M$ 关闭电源。此外，该灯允许你设置一个切换其状态（状态为“灯亮”和“灯灭”）的程序。不幸的是，灯中已经预装了一个程序。
该灯只允许使用 _良好_ 程序。良好程序可以用一个非空数组 $a$ 表示，其中 $0 < a_1 < a_2 < dots.h < a_(| a |) < M$。所有 $a_i$ 必须是整数。当然，预装程序是一个良好程序。
灯按照程序 $a$ 以下方式运行：在时刻 $0$ 开启电源并点亮灯光。然后在时刻 $a_i$，灯会立即切换其状态（如果灯亮则关闭，反之亦然）。例如，如果你在时刻 $1$ 关闭灯光，然后不做任何操作，灯亮的总时间为 $1$。最后，在时刻 $M$，无论灯处于何种状态，电源都会被关闭。
由于你不是那些阅读说明书的人，也不理解其使用的语言，经过一些测试后，你意识到唯一可能修改预装程序的方法是：你可以 *至多插入一个* 元素到程序 $a$ 中，使得修改后的程序仍然是一个 _良好_ 程序。插入可以在 $a$ 中任意一对相邻元素之间进行，甚至可以在开头或末尾插入。
找到一种修改程序的方式，使得灯亮的总时间最大化。你也可以选择不修改程序。如果灯从时刻 $x$ 亮到时刻 $y$，则其亮了 $y - x$ 单位时间。所有灯亮的时间段相加。
第一行包含两个用空格分隔的整数 $n$ 和 $M$ ($1 lt.eq n lt.eq 10^5$, $2 lt.eq M lt.eq 10^9$) —— 程序 $a$ 的长度和电源关闭的时刻。
第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, dots.h, a_n$ ($0 < a_1 < a_2 < dots.h < a_n < M$) —— 初始安装的程序 $a$。
输出一个整数 —— 灯亮的可能最大总时间。
在第一个例子中，一种可能的最优解是插入值 $x = 3$ 到 $a_1$ 之前，程序变为 $[ 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$。
## Input
第一行包含两个用空格分隔的整数 $n$ 和 $M$ ($1 lt.eq n lt.eq 10^5$, $2 lt.eq M lt.eq 10^9$) —— 程序 $a$ 的长度和电源关闭的时刻。第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, dots.h, a_n$ ($0 < a_1 < a_2 < dots.h < a_n < M$) —— 初始安装的程序 $a$。
## Output
输出一个整数 —— 灯亮的可能最大总时间。
[samples]
## Note
在第一个例子中，一种可能的最优解是插入值 $x = 3$ 到 $a_1$ 之前，程序变为 $[ 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$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ M \in \mathbb{Z}^+ $ with $ 1 \le n \le 10^5 $, $ 2 \le M \le 10^9 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a strictly increasing sequence of integers such that $ 0 < a_1 < a_2 < \dots < a_n < M $.
The lamp operates as follows:
- At time $ 0 $: power and light are turned **on**.
- At each $ a_i $: the lamp **flips** its state.
- At time $ M $: power is turned **off** (state is ignored).
The initial state sequence is:
- $ [0, a_1) $: **on**
- $ [a_1, a_2) $: **off**
- $ [a_2, a_3) $: **on**
- $ \dots $
- If $ n $ is even: last interval $ [a_n, M) $ is **off**
- If $ n $ is odd: last interval $ [a_n, M) $ is **on**
Let $ S(A) $ denote the total time the lamp is lit under program $ A $:
$$
S(A) = \sum_{i=0}^{\lfloor n/2 \rfloor} (a_{2i+1} - a_{2i}) + \begin{cases}
M - a_n & \text{if } n \text{ is odd} \\
0 & \text{if } n \text{ is even}
\end{cases}
$$
where $ a_0 = 0 $, and indices are 1-based.
We are allowed to **insert at most one integer** $ x $ into $ A $, such that the resulting sequence $ A' $ remains strictly increasing and satisfies $ 0 < x < M $, and $ x \notin A $.
Let $ \mathcal{I} $ be the set of all possible insertion positions:
- Before $ a_1 $: $ x \in (0, a_1) $
- Between $ a_i $ and $ a_{i+1} $: $ x \in (a_i, a_{i+1}) $ for $ i = 1, \dots, n-1 $
- After $ a_n $: $ x \in (a_n, M) $
**Objective**
Maximize $ S(A') $ over all possible $ A' $ obtained by inserting **at most one** element into $ A $ (including the option of no insertion).
That is, compute:
$$
\max\left( S(A), \max_{x \in \mathcal{X}} S(A \cup \{x\}) \right)
$$
where $ \mathcal{X} = \bigcup_{i=0}^{n} (a_i, a_{i+1}) $, with $ a_0 = 0 $, $ a_{n+1} = M $, and $ A \cup \{x\} $ is sorted.
API Response (JSON)
{
"problem": {
"name": "B. Light It Up",
"description": {
"content": "Recently, you bought a brand new smart lamp with programming features. At first, you set up a schedule to the lamp. Every day it will turn power on at moment $0$ and turn power off at moment $M$. More",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1000B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Recently, you bought a brand new smart lamp with programming features. At first, you set up a schedule to the lamp. Every day it will turn power on at moment $0$ and turn power off at moment $M$. More...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "最近，你购买了一盏具有编程功能的全新智能灯。最初，你为灯设置了计划：每天它会在时刻 $0$ 开启电源，在时刻 $M$ 关闭电源。此外，该灯允许你设置一个切换其状态（状态为“灯亮”和“灯灭”）的程序。不幸的是，灯中已经预装了一个程序。\n\n该灯只允许使用 _良好_ 程序。良好程序可以用一个非空数组 $a$ 表示，其中 $0 < a_1 < a_2 < dots.h < a_(| a |) < M$。所...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $, $ M \\in \\mathbb{Z}^+ $ with $ 1 \\le n \\le 10^5 $, $ 2 \\le M \\le 10^9 $. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a strictly increasing sequence of integers...",
"is_translate": false,
"language": "Formal"
}
]
}