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.


-----Examples-----
Input
3 10
4 6 7

Output
8

Input
2 12
1 10

Output
9

Input
2 7
3 4

Output
6



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

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms
Expected Time Complexity: O(N)

Starter code:

Solutions:
(n, m) = map(int, input().split())
ls = [0] + [int(x) for x in input().split()] + [m]
lb = [0] * n
b = 0
for i in range(0, n + 1, 2):
	b += ls[i + 1] - ls[i]
ans = b
b = m - b + ls[1] - 1
if ls[1] != 1 or ls[2] - ls[1] != 1:
	ans = max(ans, b)
for i in range(1, n - 1, 2):
	b = b + ls[i] + ls[i + 2] - 2 * ls[i + 1]
	if ls[i + 2] - 1 != ls[i + 1] or ls[i + 2] + 1 != ls[i + 3]:
		ans = max(ans, b)
print(ans)


(n, m) = map(int, input().split())
aprogram = [0] + list(map(int, input().split())) + [m]
interval = []
total = 0
a = 0
sumbrightbefore = [0 for i in range(n + 1)]
sumdimafter = [0 for i in range(n + 1)]
for i in range(1, len(aprogram)):
	interval += [aprogram[i] - aprogram[i - 1]]
for i in range(2, len(interval), 2):
	sumbrightbefore[i] = sumbrightbefore[i - 2] + interval[i - 2]
for i in range(1, len(interval), 2):
	sumbrightbefore[i] = sumbrightbefore[i - 1] + interval[i - 1]
if len(interval) % 2 == 0:
	for i in range(len(interval) - 3, -1, -2):
		sumdimafter[i] = sumdimafter[i + 2] + interval[i + 2]
	for i in range(len(interval) - 2, -1, -2):
		sumdimafter[i] = sumdimafter[i + 1] + interval[i + 1]
else:
	for i in range(len(interval) - 3, -1, -2):
		sumdimafter[i] = sumdimafter[i + 2] + interval[i + 1]
	for i in range(len(interval) - 4, -1, -2):
		sumdimafter[i] = sumdimafter[i + 1]
total = sum(interval[::2])
for i in range(0, len(interval)):
	if interval[i] != 1:
		a = sumbrightbefore[i] + sumdimafter[i] + interval[i] - 1
	if a > total:
		total = a
print(total)


(n, M) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [M]
dp = [0]
m = 0
for i in range(1, n + 2):
	dp.append(dp[i - 1] + (a[i] - a[i - 1]) * (i & 1))
for i in range(1, n + 2):
	if a[i] - a[i - 1] > 1:
		if i & 1:
			m = max(m, dp[i] * 2 + M - 1 - dp[n + 1] - a[i])
		else:
			m = max(m, dp[i] * 2 - a[i - 1] - 1 + M - dp[n + 1])
print(max(dp[n + 1], m))


(a, b) = map(int, input().split())
l = list(map(int, input().split()))
l = [0] + l + [b]
lo = [0] * len(l)
li = [0] * len(l)
for i in range(1, len(l)):
	if i % 2 == 0:
		li[i] = li[i - 1] + l[i] - l[i - 1]
		lo[i] = lo[i - 1]
	else:
		lo[i] = lo[i - 1] + l[i] - l[i - 1]
		li[i] = li[i - 1]
num = lo[len(l) - 1]
for i in range(1, len(l) - 1):
	x = lo[i]
	y = li[len(l) - 1]
	z = li[i + 1]
	num = max(num, x + (y - z) + (l[i + 1] - l[i] - 1))
print(num)


(n, M) = map(int, input().split())
a = [int(x) for x in input().split()]
a.append(0)
a.append(M)
a.sort()
b = [0 for i in range(0, n + 1)]
flag = 1
for i in range(0, n + 1):
	b[i] += b[i - 1] + flag * (a[i + 1] - a[i])
	flag += pow(-1, i + 1)
ans = b[n]
for i in range(0, n + 1):
	ans = max(ans, b[i] - 1 + M - a[i + 1] - (b[n] - b[i]))
print(ans)


(n, m) = map(lambda x: int(x), input().split())
num = input()
list = [int(x) for x in num.split()]
list.append(0)
list.append(m)
list.sort()
l1 = []
l2 = []
w = []
for i in range(1, n + 2, 2):
	l1.append(list[i] - list[i - 1])
	if i < n + 1:
		l2.append(list[i + 1] - list[i])
a = sum(l1)
if len(l1) == len(l2):
	b = a - 1 + l2[-1]
	w.append(b)
	for i in range(1, len(l1)):
		b = b - l1[-i] + l2[-(i + 1)]
		w.append(b)
else:
	b = a - l1[-1] - 1 + l2[-1]
	w.append(b)
	for i in range(1, len(l2)):
		b = b - l1[-(i + 1)] + l2[-(i + 1)]
		w.append(b)
w.append(a)
print(max(w))


from itertools import *
R = lambda : map(int, input().split())
(n, m) = R()
a = [0, *R()] + [m] * (n % 2 + 1)
d = [x - y for (x, y) in zip(a[1:], a)]
print(sum(d[::2]) + max(1, *accumulate((d[i - 1] - d[i] for i in range(n + n % 2, 0, -2)))) - 1)


(a, b) = map(int, input().split())
list = [int(x) for x in input().split()]
if not a % 2:
	a += 1
	list.append(b)
time = sum(list[0:a:2]) - sum(list[1:a:2])
alter = b - 1 - list[a - 1]
addtime = max(alter, 0)
for i in range(a - 3, -1, -2):
	alter += list[i + 1] * 2 - list[i] - list[i + 2]
	addtime = max(addtime, alter)
print(time + addtime)


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
arr.append(m)
arr1 = []
arr2 = []
for i in range(n + 1):
	if i % 2 == 0:
		if i == 0:
			arr1.append(arr[0])
		else:
			arr1.append(arr1[-1] + arr[i] - arr[i - 1])
	elif i > 1:
		arr2.append(arr2[-1] + arr[i] - arr[i - 1])
	else:
		arr2.append(arr[i] - arr[i - 1])
ans = arr1[-1]
if n % 2 != 0:
	for i in range(0, n, 2):
		ans1 = 0
		if i > 0:
			ans1 = arr1[i // 2] - 1 + (arr2[-1] - arr2[i // 2 - 1])
		else:
			ans1 = arr1[i // 2] - 1 + arr2[-1]
		if ans1 > ans:
			ans = ans1
else:
	for i in range(0, n, 2):
		ans1 = 0
		if i > 0:
			ans1 = arr1[i // 2] - 1 + (arr2[-1] - arr2[i // 2 - 1])
		else:
			ans1 = arr1[i // 2] - 1 + arr2[-1]
		if ans1 > ans:
			ans = ans1
print(ans)


(n, m) = map(int, input().split())
a = [int(x) for x in input().split()]
b = []
a.insert(0, 0)
if n % 2 == 0:
	a.insert(n + 1, m)
	k = sum(((-1) ** (i + 1) * a[i] for i in range(n + 2)))
else:
	k = sum(((-1) ** (i + 1) * a[i] for i in range(n + 1)))
l = m - k + a[1] - 1
b += [k, l]
for i in range(1, (n + 1) // 2):
	l += a[2 * i - 1] + a[2 * i + 1] - 2 * a[2 * i]
	b += [l]
print(int(max(b)))


(n, M) = map(int, input().split())
a = [int(i) for i in input().split()]
a.insert(0, 0)
a.append(M)
on = off = 0
for i in range(1, len(a), 2):
	on += a[i] - a[i - 1]
answer = on
for i in range(2, len(a), 2):
	off += a[i - 1] - a[i - 2]
	if a[i] > a[i - 1] + 1:
		answer = max(answer, off + M - a[i - 1] - 1 - (on - off))
print(answer)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.insert(0, 0)
a.append(m)
sz = len(a)
f = [[0] * sz for i in range(2)]
for i in range(sz - 2, -1, -1):
	f[0][i] = f[1][i + 1]
	f[1][i] = a[i + 1] - a[i] + f[0][i + 1]
ans = f[1][0]
for i in range(sz - 1):
	if a[i + 1] - a[i] < 2:
		continue
	idx = i & 1 ^ 1
	sm = f[1][0] - f[idx][i]
	ans = max(ans, sm + (a[i + 1] - a[i] - 1) + f[idx][i + 1])
print(ans)


(n, m) = map(int, input().split())
list1 = [0] + [int(x) for x in input().split()] + [m]
a = b = c = 0
for i in range(1, len(list1), 2):
	a = a + list1[i] - list1[i - 1]
b = a
for i in range(2, len(list1), 2):
	c = c + list1[i - 1] - list1[i - 2]
	if list1[i] > list1[i - 1] + 1:
		d = a - c
		b = max(b, c + m - list1[i - 1] - 1 - d)
print(b)


import sys
from array import array
(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [m]
(acc1, acc2) = ([0] * (n + 2), [0] * (n + 2))
for i in range(n, -1, -1):
	acc1[i] = acc1[i + 1]
	acc2[i] = acc2[i + 1]
	if i & 1:
		acc2[i] += a[i + 1] - a[i]
	else:
		acc1[i] += a[i + 1] - a[i]
ans = acc1[0]
for i in range(1, n + 1):
	if a[i - 1] + 1 < a[i]:
		if i & 1:
			ans = max(ans, acc1[0] - acc1[i] - 1 + acc2[i])
		else:
			ans = max(ans, acc1[0] - acc1[i] + 1 + acc2[i])
	if a[i] + 1 < a[i + 1]:
		if i & 1:
			ans = max(ans, acc1[0] - acc1[i] + acc2[i] - 1)
		else:
			ans = max(ans, acc1[0] - acc1[i] + 1 + acc2[i])
print(ans)


(n, M) = map(int, input().split())
l1 = [int(x) for x in input().split()]
l2 = []
pre = 0
pre1 = -10 ** 30
for i in range(n):
	pre += (-1) ** i * l1[i]
	l2.append(pre)
s = set(l1)
for i in range(n):
	b = -10 ** 30
	if i == 0 and l1[i] != 1:
		b = l1[i] - 1 - pre
	elif i >= 1 and l1[i] - 1 not in s:
		b = 2 * l2[i - 1] + (-1) ** i * (l1[i] - 1) - pre
	pre1 = max(pre1, b)
for i in range(n):
	c = -10 ** 30
	if i == n - 1 and l1[-1] != M - 1:
		c = pre + (-1) ** n * (l1[-1] + 1)
	elif i <= n - 1 and l1[i] + 1 not in s:
		c = 2 * l2[i] + (-1) ** (i + 1) * (l1[i] + 1) - pre
	pre1 = max(pre1, c)
if n % 2 == 0:
	print(max(pre + M, pre1))
else:
	print(max(pre, pre1 + M))


(n, M) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [M]
t = 0
for k in range(1, len(a), 2):
	t += a[k] - a[k - 1]
s = -t + a[1] - 1 + M
t = max(s, t)
for i in range(3, n + 1, 2):
	s = s + a[i - 2] - 2 * a[i - 1] + a[i]
	if a[i] - a[i - 1] > 1 or a[i + 1] - a[i] > 1:
		t = max(s, t)
print(t)


import collections
from functools import cmp_to_key
import math
import sys

def getIntList():
	return list(map(int, input().split()))
import bisect
try:
	import numpy
	dprint = print
	dprint('debug mode')
except ModuleNotFoundError:

	def dprint(*args, **kwargs):
		pass

def makePair(z):
	return [(z[i], z[i + 1]) for i in range(0, len(z), 2)]

def memo(func):
	cache = {}

	def wrap(*args):
		if args not in cache:
			cache[args] = func(*args)
		return cache[args]
	return wrap

@memo
def comb(n, k):
	if k == 0:
		return 1
	if n == k:
		return 1
	return comb(n - 1, k - 1) + comb(n - 1, k)
(N, M) = getIntList()
z = [0] + getIntList() + [M]
z1 = [z[i + 1] - z[i] for i in range(N + 1)]
zl0 = [0]
zl1 = [0]
for i in range(N + 1):
	if i % 2 == 0:
		zl0.append(zl0[-1] + z1[i])
		zl1.append(zl1[-1])
	else:
		zl0.append(zl0[-1])
		zl1.append(zl1[-1] + z1[i])
zr0 = [0 for i in range(N + 2)]
zr1 = [0 for i in range(N + 2)]
for i in range(N, -1, -1):
	if i % 2 == 0:
		zr0[i] = zr0[i + 1] + z1[i]
		zr1[i] = zr1[i + 1]
	else:
		zr0[i] = zr0[i + 1]
		zr1[i] = zr1[i + 1] + z1[i]
res = zl0[-1]
for i in range(N + 1):
	t = zl0[i] + z1[i] - 1 + zr1[i + 1]
	res = max(res, t)
print(res)


(n, m) = [int(x) for x in input().split()]
a = [int(y) for y in input().split()]
a.append(0)
a.sort()
f = 1
k = 0
maximum = 0
for i in range(n):
	time = f * (a[i + 1] - a[i])
	f *= -1
	if time < -1:
		maximum = max(maximum, k - 1)
	k += time
	if k > 1:
		maximum = max(maximum, k - 1)
k += (1 - 2 * (n % 2)) * (m - a[n])
maximum = max(maximum, k)
print(maximum + (m - k) // 2)


(n, M) = input().split(' ')
n = int(n)
M = int(M)
split = []
light_time = 0
dark_time = 0
inv = input().split(' ')
inv = [int(i) for i in inv]
for i in range(n + 1):
	if i == 0:
		split.append(inv[0] - 0)
	elif i == n:
		split.append(M - inv[-1])
	else:
		split.append(inv[i] - inv[i - 1])
	if i % 2 == 0:
		light_time += split[i]
	else:
		dark_time += split[i]
dealt_light = 0
dealt_dark = 0
act_light = 0
max_light = light_time
for i in range(n + 1):
	if i % 2 == 0:
		light_time -= split[i]
		if split[i] != 1:
			act_light = dark_time + dealt_light - 1 + split[i]
		dealt_light += split[i]
	else:
		dark_time -= split[i]
		if split[i] != 1:
			act_light = dark_time + dealt_light - 1 + split[i]
		dealt_dark += split[i]
	if act_light > max_light:
		max_light = act_light
print(max_light)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
s1 = [0] * (n + 1)
s2 = [0] * (n + 1)
s1[0] = a[0]
a.append(m)
n += 1
for i in range(1, n):
	if i % 2 == 0:
		s1[i] = s1[i - 1] + a[i] - a[i - 1]
		s2[i] = s2[i - 1]
	else:
		s2[i] = s2[i - 1] + a[i] - a[i - 1]
		s1[i] = s1[i - 1]
sum1 = s1[n - 1]
sum2 = s2[n - 1]
ans = sum1
for i in range(n - 1):
	if i % 2 == 0:
		ans = max(ans, s1[i] - 1 + sum2 - s2[i])
	else:
		ans = max(ans, s1[i] + sum2 - s2[i])
print(ans)


from math import ceil, log
t = 1
for test in range(t):
	(n, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.append(m)
	prev = 0
	on = 0
	counter = 0
	for i in arr:
		if counter % 2 == 0:
			on += i - prev
		prev = i
		counter += 1
	off = m - on
	counter = 0
	ans = on
	prev = 0
	prevOn = 0
	for i in arr:
		if counter % 2 == 0:
			if i - prev != 1:
				tmp = prevOn + i - prev - 1 + m - i - (on - prevOn - (i - prev))
				if tmp > ans:
					ans = tmp
			prevOn += i - prev
		elif i - prev != 1:
			tmp = prevOn + i - prev - 1 + m - i - (on - prevOn)
			if tmp > ans:
				ans = tmp
		prev = i
		counter += 1
	print(ans)


(n, M) = map(int, input().split())
A = list(map(int, input().split()))
A = [0] + A + [M]
D = []
for i in range(n + 1):
	D.append(A[i + 1] - A[i])
E = []
O = []
for (i, d) in enumerate(D):
	if i % 2 == 0:
		E.append(d)
		O.append(0)
	else:
		O.append(d)
		E.append(0)
from itertools import accumulate
CE = [0] + E
CE = list(accumulate(CE))
CO = [0] + O
CO = list(accumulate(CO))
ans = CE[-1]
for i in range(n + 1):
	if D[i] == 1:
		continue
	temp = CE[i] + (D[i] - 1) + CO[-1] - CO[i + 1]
	ans = max(ans, temp)
print(ans)


(n, M) = list(map(int, input().split()))
A = [0] + list(map(int, input().split())) + [M]
total_on = 0
for (i, a) in enumerate(A):
	if i % 2:
		total_on += a - A[i - 1]
on = [[M - total_on] * (n + 2), [total_on] * (n + 2)]
for i in range(1, n + 2):
	sw = i % 2
	on[sw][i] = on[sw][i - 1] - (A[i] - A[i - 1])
	on[1 - sw][i] = on[1 - sw][i - 1]
maxon = total_on
for i in range(n + 1):
	if A[i] < A[i + 1] - 1:
		maxon = max(maxon, total_on + on[0][i + 1 - i % 2] - on[1][i + 1] - 1)
print(maxon)


f = 1
(n, M) = map(int, input().split())
a = [0] + [int(x) for x in input().split()] + [M]
b = [0] * (n + 2)
for i in range(1, n + 1):
	b[i] = b[i - 1] + f * (a[i] - a[i - 1])
	f ^= 1
b[n + 1] = b[n] + f * (M - a[n])
ans = b[n + 1]
for i in range(1, n + 2):
	if a[i] - a[i - 1] > 1:
		if i & 1:
			ans = max(ans, b[i] + M - a[i] - (b[n + 1] - b[i]) - 1)
		else:
			ans = max(ans, b[i] + a[i] - a[i - 1] - 1 + M - a[i] - (b[n + 1] - b[i]))
print(ans)


(n, M) = map(int, input().split())
s = [int(x) for x in input().split()]
ss = [s[0]]
so = []
se = []
for i in range(n - 1):
	ss.append(s[i + 1] - s[i])
ss.append(M - s[n - 1])
if (n + 1) % 2 == 1:
	for i in range(int(n / 2)):
		so.append(ss[2 * i])
		se.append(ss[2 * i + 1])
	so.append(ss[n])
	sss = sum(so)
	a = 0
	b = sum(se)
	for i in range(len(se)):
		a += so[i]
		if i != 0:
			b -= se[i - 1]
		m = a + b - 1
		if m > sss:
			sss = m
	print(sss)
else:
	for i in range(int((n + 1) / 2)):
		so.append(ss[2 * i])
		se.append(ss[2 * i + 1])
	sss = sum(so)
	a = 0
	b = sum(se)
	for i in range(len(so)):
		a += so[i]
		if i != 0:
			b -= se[i - 1]
		m = a + b - 1
		if m > sss:
			sss = m
	print(sss)


def main():
	(n, M) = [int(i) for i in input().split(' ')]
	a = [0] + [int(i) for i in input().split(' ')] + [M]
	n = n + 2
	incr_sum = []
	s = 0
	for i in range(n):
		if i % 2 == 1:
			s += a[i] - a[i - 1]
		incr_sum.append(s)
	max_sum = s
	for i in range(n - 1):
		if a[i + 1] - a[i] != 1:
			to_add = a[i + 1] - 1
			s_ = incr_sum[i]
			s_ += to_add - a[i]
			s_ += a[-1] - a[i + 1] - (incr_sum[-1] - incr_sum[i + 1])
			if s_ > max_sum:
				max_sum = s_
	print(max_sum)
main()


(n, m) = map(int, input().split())
a = [int(x) for x in input().split()]
a.insert(0, 0)

def count(data):
	k = m * (1 + (-1) ** (len(data) + 1)) / 2
	for i in range(len(data)):
		k += (-1) ** (i % 2 + 1) * data[i]
	return k
b = [count(a)]
a.insert(1, a[1] - 1)
k = count(a)
if a[1] - 1 > 1:
	b += [k]
del a[1]
for i in range(n + n % 2 - 1):
	if i % 2 == 1:
		k += -2 * a[i + 1] + a[i] + a[i + 2]
	j = a[i // 2 * 2 + 1] + (-1) ** i
	if j < m and (i // 2 * 2 + 1 + (-1) ** i > n or j != a[i // 2 * 2 + 1 + (-1) ** i]):
		b += [k]
print(int(max(b)))


(n, M) = [int(x) for x in input().split()]
lst0 = [int(x) for x in input().split()]
lst = [lst0[0]]
for i in range(0, n - 1):
	lst.append(lst0[i + 1] - lst0[i])
lst.append(M - lst0[-1])
L = D = 0
for i in range(1, n + 1, 2):
	D = D + lst[i]
for i in range(2, n + 1, 2):
	L = L + lst[i]
lstL = [L]
lstD = [D]
lstW = [D - L - 1]
for i in range(2, n + 1):
	if i % 2 == 0:
		D = D - lst[i - 1]
		W = D - L + lst[i - 1] - 1
		lstL.append(L)
		lstD.append(D)
		lstW.append(W)
	else:
		L = L - lst[i - 1]
		W = D - L - 1
		lstL.append(L)
		lstD.append(D)
		lstW.append(W)
lstL.append(0)
lstD.append(0)
if n % 2 == 0:
	lstW.append(-1)
else:
	lstW.append(M - lst0[-1] - 1)
if max(lstW) > 0:
	k = lstW.index(max(lstW)) + 1
	lk = 0
	if k % 2 == 1:
		for i in range(0, k, 2):
			lk = lk + lst[i]
			ans = lk + lstD[k - 1] - 1
	else:
		for i in range(0, k - 1, 2):
			lk = lk + lst[i]
			ans = lk + lstD[k - 1] + lst[k - 1] - 1
else:
	ans = 0
	for i in range(0, n + 1, 2):
		ans = ans + lst[i]
print(ans)


(n, m) = map(int, input().split())
aprogram = [0] + list(map(int, input().split())) + [m]
s = [0]
for i in range(len(aprogram) - 1):
	s += [s[-1]]
	if i % 2 == 0:
		s[-1] += aprogram[i + 1] - aprogram[i]
print(max([s[-1]] + [s[i] + s[i - 1] + m - s[-1] - aprogram[i - 1] - 1 for i in range(1, len(aprogram))]))


(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [m]
ans = 0
work = []
isOn = True
for i in range(1, n + 2, 2):
	work.append(a[i] - a[i - 1])
fin = [0, work[-1]]
for i in range(len(work) - 2, -1, -1):
	fin.append(work[i] + fin[-1])
cur = 0
for i in range(1, n + 1, 2):
	cur += work[i // 2]
	ans = max(ans, m - 1 - a[i] - fin[len(fin) - 2 - i // 2] + cur)
print(max(ans, fin[-1]))


from sys import stdin, exit, setrecursionlimit
setrecursionlimit(100000000)
from math import *
from bisect import bisect_left
from collections import deque
input = stdin.readline
lmi = lambda : list(map(int, input().split()))
mi = lambda : map(int, input().split())
si = lambda : input().strip('\n')
ssi = lambda : input().strip('\n').split()
(n, m) = mi()
a = [0] + lmi() + [m]
arr = [0] * (n + 3)
arr2 = [0] * (n + 3)
for i in range(1, n + 2, 2):
	arr[i] += a[i] - a[i - 1]
for i in range(2, n + 2, 2):
	arr2[i] += a[i] - a[i - 1]
for i in range(1, n + 3):
	arr[i] += arr[i - 1]
for i in range(n + 1, -1, -1):
	arr2[i] += arr2[i + 1]
ans = arr[-1]
for i in range(n + 3):
	ans = max(ans, arr[i] + arr2[i] - 1)
print(ans)


(n, m) = map(int, input().split())
a = [0] + [int(x) for x in input().split()] + [m]
tot = ans = s = 0
for i in range(1, len(a), 2):
	tot += a[i] - a[i - 1]
ans = tot
for i in range(2, len(a), 2):
	s += a[i - 1] - a[i - 2]
	if a[i] > a[i - 1] + 1:
		t = tot - s
		ans = max(ans, s + m - a[i - 1] - 1 - t)
print(ans)


nm = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a.insert(0, 0)
a.append(nm[1])
nm[0] += 2
tactsum = 0
tdeactsum = 0
tact = []
tdeact = []
for i in range(1, nm[0]):
	if i % 2 == 1:
		tact.append(a[i] - a[i - 1] + tactsum)
		tdeact.append(tdeactsum)
		tactsum += a[i] - a[i - 1]
	else:
		tdeact.append(a[i] - a[i - 1] + tdeactsum)
		tact.append(tactsum)
		tdeactsum += a[i] - a[i - 1]
max = tactsum
for i in range(nm[0] - 2):
	x = -1
	if a[i + 1] != a[i + 2] - 1:
		x = a[i] + 1
		if tdeact[nm[0] - 2] - tdeact[i] + tact[i] - 1 > max:
			max = tdeact[nm[0] - 2] - tdeact[i] + tact[i] - 1
		x = a[i + 1] - 1
		if tdeact[nm[0] - 2] - tdeact[i + 1] + tact[i] + 1 > max:
			max = tdeact[nm[0] - 2] - tdeact[i + 1] + tact[i] + 1
print(max)


x = list(map(int, input().rstrip().split()))
y = list(map(int, input().rstrip().split()))
y.append(x[1])
l = [0] * (x[0] + 1)
m = [0] * (x[0] + 1)
used = 0
unused = 0
m[0] = y[0]
used = y[0]
for i in range(1, x[0] + 1):
	if i % 2 == 1:
		unused = unused + y[i] - y[i - 1]
		l[i] = unused
		m[i] = used
	else:
		used = used + y[i] - y[i - 1]
		l[i] = unused
		m[i] = used
mi = m[-1]
for i in range(x[0]):
	if i != 0 and y[i] - 1 != y[i - 1]:
		if i % 2 == 0:
			mi = max(mi, m[i] + l[-1] - l[i] - 1)
		else:
			mi = max(mi, m[i] + l[-1] - l[i] + 1)
	else:
		mi = max(mi, m[i] + l[-1] - l[i] - 1)
if x[0] % 2 == 1 and y[x[0] - 1] != x[1] - 1:
	mi = max(mi, m[-1] + 1)
print(mi)


(n, t) = map(int, input().split())
l0 = list(map(int, input().split()))
l1 = [0]
l2 = []
l1.extend(l0)
l2.extend(l0)
l2.append(t)
d1 = list(map(lambda x, y: x - y, l2, l1))
if n % 2 == 1:
	d2 = [d1[-1] - 1]
	del d1[-1]
else:
	d2 = [-1]
for x in range(n // 2):
	d2.append(d2[x] - d1[-2 * x - 1] + d1[-2 * x - 2])
d2.append(0)
print(sum(d1[::2]) + max(d2))


def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())
(n, M) = mi()
a = [0] + li() + [M]
n = len(a)
ans = 0
p = [0] * n
q = [0] * n
for i in range(1, n):
	p[i] = p[i - 1]
	q[i] = q[i - 1]
	if i % 2 == 0:
		p[i] += a[i] - a[i - 1]
	else:
		q[i] += a[i] - a[i - 1]
ans = q[-1]
for i in range(1, n):
	if a[i] == a[i - 1] + 1:
		continue
	if i % 2 == 0:
		ans = max(ans, q[i] + 1 + p[-1] - p[i], q[i] + a[i] - a[i - 1] - 1 + p[-1] - p[i])
	else:
		ans = max(ans, q[i] - 1 + p[-1] - p[i], q[i] - (a[i] - a[i - 1] - 1) + p[-1] - p[i])
print(ans)


(n, m) = list(map(int, input().split()))
c = list(map(int, input().split()))
f = [0] * n
gor = 0
for i in range(n):
	if i % 2 == 0 and i > 0:
		gor += c[i] - c[i - 1]
	elif i % 2 == 0:
		gor += c[i]
	f[i] = gor
if n % 2 == 0:
	gor += m - c[n - 1]
ma = gor
if c[0] > 1:
	if m - gor + 1 > ma:
		ma = m - gor + 1
for i in range(n):
	if i != n - 1:
		if c[i + 1] - c[i] > 1:
			if i % 2 == 0:
				t = m - c[i] - 1 - (gor - f[i])
			else:
				t = m - (c[i + 1] - 1) - (gor - (f[i + 1] - 1))
			if t + f[i] > ma:
				ma = t + f[i]
	elif m - c[i] > 1:
		if n % 2 == 1:
			t = gor + m - c[i] - 1
			if ma < t:
				ma = gor + m - c[i] - 1
print(ma)


from sys import stdin, stdout
get_string = lambda : stdin.readline().strip('\n')
get_intmap = lambda : map(int, get_string().split(' '))

def testcase():
	(n, M) = get_intmap()
	a = [0] + list(get_intmap()) + [M]
	ontime = [0] * (n + 1)
	tmp = 0
	for ind in range(n, -1, -1):
		if ind % 2 == 0:
			tmp += a[ind + 1] - a[ind]
		ontime[ind] = tmp
	mx = ontime[0]
	for ind in range(n + 1):
		(l, r) = (a[ind], a[ind + 1])
		if r - l <= 1:
			continue
		for x in (l + 1, r - 1):
			newtime = ontime[0] - ontime[ind]
			if ind % 2 == 0:
				newtime += x - l
			else:
				newtime += r - x
			newtime += M - r - ontime[ind]
			mx = max(mx, newtime)
	print(mx)
testcase()
quit()
for t in range(int(input())):
	testcase()


(n, m) = [int(x) for x in input().split()]
a = [0] + [int(x) for x in input().split()]
prev = m
pos = 0
neg = 0
on = n % 2 == 0
max_diff = 0
for i in range(n, -1, -1):
	adv = prev - a[i]
	if not on:
		diff = neg - pos + adv - 1
		max_diff = max(max_diff, diff)
		neg += adv
	else:
		pos += adv
	on = not on
	prev = a[i]
print(pos + max_diff)


(n, M) = map(int, input().split(' '))

def keep(p):
	front = [p[0]]
	for i in range(1, len(p)):
		if not i % 2:
			front.append(front[i - 1] + p[i] - p[i - 1])
		else:
			front.append(front[i - 1])
	back = []
	for i in range(0, len(p)):
		back.append(p[-1] - p[i] - front[len(p) - 1] + front[i])
	return (front, back)
program = list(map(int, input().split(' ')))
program.append(M)
(front, back) = keep(program)
time = program[0] - 1 + back[0]
for i in range(1, len(program)):
	if program[i] != program[i - 1] + 1:
		time = max(time, program[i] - program[i - 1] - 1 + back[i] + front[i - 1])
time = max(time, front[len(program) - 1])
print(time)


(n, m) = input().split()
n = int(n)
m = int(m)
ai = [int(a) for a in input().split()]
if not (len(ai) == 2 and ai[1] - ai[0] == 1):
	ai = [0] + ai + [m]
	state = True
	shining_time_orig = 0
	for (i, a) in enumerate(ai[1:-1], 1):
		if state:
			shining_time_orig += ai[i] - ai[i - 1]
			state = False
		else:
			state = True
	if state:
		shining_time_orig += ai[-1] - ai[-2]
	ai_c = list(ai)
	ai_c.insert(2, ai_c[1] + 1)
	state = True
	shining_time_c = 0
	for (i, a) in enumerate(ai_c[1:-1], 1):
		if state:
			shining_time_c += ai_c[i] - ai_c[i - 1]
			state = False
		else:
			state = True
	if state:
		shining_time_c += ai_c[-1] - ai_c[-2]
	state = True
	saved_state = None
	biggest_gap = 0
	biggest_gap_index = None
	for (i, a) in enumerate(ai[1:-1], 1):
		if state:
			state = False
		else:
			state = True
		gap = ai[i] - ai[i - 1]
		if gap > 1:
			if gap > biggest_gap or (gap == biggest_gap and (not state)):
				biggest_gap = gap
				biggest_gap_index = i
				saved_state = state
	if biggest_gap:
		if saved_state:
			ai.insert(biggest_gap_index, ai[biggest_gap_index - 1] + 1)
		else:
			ai.insert(biggest_gap_index, ai[biggest_gap_index] - 1)
else:
	ai = [0] + ai + [m]
	shining_time_c = 0
	shining_time_orig = 0
state = True
shining_time = 0
for (i, a) in enumerate(ai[1:-1], 1):
	if state:
		shining_time += ai[i] - ai[i - 1]
		state = False
	else:
		state = True
if state:
	shining_time += ai[-1] - ai[-2]
print(max(shining_time, shining_time_c, shining_time_orig))


(n, m) = map(int, input().split())
l = [0] + [int(x) for x in input().split()] + [m]
b = [0] * (n + 2)
for i in range(1, len(l)):
	if int(i) % 2 != 0:
		b[i] += b[i - 1] + l[i] - l[i - 1]
	else:
		b[i] = b[i - 1]
ans = b[-1]
for i in range(1, n + 2):
	if l[i] - l[i - 1] > 1:
		if int(i) % 2 == 1:
			ans = max(ans, b[i] + m - l[i] - (b[n + 1] - b[i]) - 1)
		else:
			ans = max(ans, b[i] + l[i] - l[i - 1] - 1 + m - l[i] - (b[n + 1] - b[i]))
print(ans)


(n, M) = map(int, input().split())
x = [0] + [int(t) for t in input().split()] + [M]
light = [x[i + 1] - x[i] for i in range(n + 1)]
oddleft = [0]
presum = [0]
for i in range(len(light)):
	if i % 2 == 0:
		oddleft.append(oddleft[-1] + light[i])
	else:
		oddleft.append(oddleft[-1])
	presum.append(light[i] + presum[-1])
res = max(oddleft[-1], presum[-1] - oddleft[-1])
for i in range(len(light)):
	if light[i] > 1:
		res = max(res, oddleft[i] + light[i] - 1 + presum[-1] - presum[i + 1] - (oddleft[-1] - oddleft[i + 1]))
print(res)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
a = [0] + a + [m]
d = [0] * (n + 1)
for i in range(n + 1):
	d[i] = a[i + 1] - a[i]
fwd = [0] * len(a)
s = 0
for i in range(1, len(a)):
	if i % 2 == 1:
		s += d[i - 1]
		fwd[i] = s
	else:
		fwd[i] = fwd[i - 1]
bwd = [0] * len(a)
s = 0
for i in range(1, len(a)):
	if (len(a) - 1 - i) % 2 == 0:
		s += d[-i]
		bwd[-i - 1] = s
	else:
		bwd[-i - 1] = bwd[-i]
from itertools import accumulate
fwd_ = list(accumulate([0] + d))
bwd_ = list(accumulate([0] + d[::-1]))[::-1]
maxx = fwd[-1]
for i in range(n + 1):
	if a[i + 1] - a[i] > 1:
		if i % 2 == 0:
			x = fwd[i] + a[i + 1] - a[i] - 1 + bwd_[i + 1] - bwd[i + 1]
		else:
			x = fwd[i] + a[i + 1] - a[i] - 1 + bwd_[i + 1] - bwd[i + 1]
		if x > maxx:
			maxx = x
print(maxx)


(_, M) = input().split()
a = map(int, (input() + ' ' + M).split())
patch = True
max = 0
on_before = off_before = 0
previous = 0
for x in a:
	if patch:
		pre_comp = False
		patch_len = x - previous
		on_before += patch_len
		if patch_len != 1:
			d = on_before - off_before
			if d > max:
				max = d
			pre_comp = True
	else:
		patch_len = x - previous
		if not pre_comp and patch_len != 1:
			d = on_before - off_before
			if d > max:
				max = d
		off_before += patch_len
	previous = x
	patch = not patch
max += off_before - 1
if on_before > max:
	max = on_before
print(max)


(n, M) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [M]
diffs = [(i % 2 == 0, e - s) for (i, (s, e)) in enumerate(zip(a[:-1], a[1:]))]
d = [(0, 0)]
for (on, x) in reversed(diffs):
	(offtime, ontime) = d[-1]
	if on:
		d.append((offtime, ontime + x))
	else:
		d.append((offtime + x, ontime))
max_diff = max((off - on for (off, on) in d))
print(sum((x for (on, x) in diffs if on)) + max(max_diff - 1, 0))


a = input().split()
n = int(a[0])
m = int(a[1])
str1 = input().split()
str2 = [0] + [int(x) for x in str1]
str2.append(m)
c = [0] * (n + 2)
d = [0] * (n + 2)
for i in range(1, n + 2):
	b = str2[i] - str2[i - 1]
	if i % 2 == 0:
		c[i] = c[i - 1]
		d[i] = d[i - 1] + b
	else:
		c[i] = c[i - 1] + b
		d[i] = d[i - 1]
e = c[-1]
for i in range(n + 1):
	if str2[i + 1] - str2[i] != 1:
		if i % 2 == 0:
			e = max(c[i + 1] + d[-1] - d[i + 1] - 1, e, c[i] + d[-1] - d[i] + 1)
		else:
			e = max(c[i + 1] + d[-1] - d[i + 1] + 1, e, c[i] + d[-1] - d[i] - 1)
print(e)


import time
(n, M) = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
start = time.time()
now = 0
x = []
for i in range(n):
	x.append(a[i] - now)
	now = a[i]
x.append(M - now)
ans = 0
ro = 0
le = 0
now = 0
for i in range(len(x)):
	if i % 2 == 1:
		ro += x[i]
	else:
		ans += x[i]
for i in range(len(x)):
	if x[i] > 1:
		now = le + ro - 1
	if now > ans:
		ans = now
	if i % 2 == 1:
		ro -= x[i]
	else:
		le += x[i]
print(ans)
finish = time.time()


(n, m) = map(int, input().split())
tm = [int(i) for i in input().split()]
sum_d = 0
sum_l = 0
is_dark = n & 1
lst = m
tm.reverse()
tm.append(0)
Max = -1
for i in tm:
	dis = lst - i
	if is_dark:
		sum_d += dis
	else:
		sum_l += dis
	lst = i
	if dis == 1:
		is_dark ^= 1
		continue
	if is_dark:
		fake_l = sum_d - 1
	else:
		fake_l = sum_d + dis - 1
	is_dark ^= 1
	Max = max(Max, fake_l - sum_l)
ans = sum_l
if Max > 0:
	ans += Max
print(ans)


(n, M) = map(int, input().split())
li = input().split()
l = []
l.append(int(0))
for j in range(len(li)):
	l.append(int(li[j]))
l.append(M)
a = []
b = []
for i in range(len(l) - 1):
	if i % 2 == 0:
		a.append(l[i + 1] - l[i])
	else:
		b.append(l[i + 1] - l[i])
s = sum(a)
sa = 0
sb = sum(b)
for i in range(len(b)):
	p = a[i] + sa + sb - 1
	if p > s and a[i] > 1:
		s = p
	sa += a[i]
	sb -= b[i]
sa = 0
sb = sum(b)
for i in range(len(b)):
	sa += a[i]
	sb -= b[i]
	p = b[i] + sa + sb - 1
	if p > s and b[i] > 1:
		s = p
print(s)


(n, M) = map(int, input().split())
a = [0] + [int(x) for x in input().split()] + [M]
t1 = []
t2 = []
for i in range(n + 1):
	if i % 2 == 0:
		t1.append(a[i + 1] - a[i])
	else:
		t2.append(a[i + 1] - a[i])
t2.append(0)
import math
ans = sum(t1)
p = 0
q = sum(t2)
for i in range(math.ceil(n / 2)):
	p = p + t1[i]
	q = q - t2[i - 1]
	ans = max(ans, p + q - 1)
print(ans)


(n, m) = map(int, input().split())
arr = [0] + list(map(int, input().split()))
arr.append(m)
narr = [(0, 0)]
sm = 0
for i in reversed(range(len(arr) - 1)):
	ns = arr[i + 1] - arr[i]
	lt = narr[-1]
	if i % 2:
		nt = (lt[0], lt[1] + ns)
	else:
		nt = (lt[0] + ns, lt[1])
		sm += ns
	narr.append(nt)
for (i, (on, off)) in enumerate(narr):
	narr[i] = max(off - on - 1, 0)
print(sm + max(narr))


(n, m) = [int(x) for x in input().split()]
a = [0] + [int(x) for x in input().split()] + [m]
s = [0]
for i in range(len(a) - 1):
	s += [s[-1]]
	if i % 2 == 0:
		s[-1] += a[i + 1] - a[i]
print(max([s[-1]] + [s[i] + s[i - 1] + m - s[-1] - a[i - 1] - 1 for i in range(1, len(a))]))


(n, m) = [int(x) for x in input().split()]
s = [int(x) for x in input().split()]
s.append(0)
s.append(m)
a = sorted(s)
b = [0] * (n + 2)
for i in range(1, n + 1):
	if i % 2 == 1:
		b[i] += b[i - 1] + a[i] - a[i - 1]
	else:
		b[i] += b[i - 1]
if n % 2 == 1:
	b[n + 1] = b[n]
else:
	b[n + 1] = b[n] + a[n + 1] - a[n]
t = b[n + 1]
for i in range(1, n + 2):
	if a[i] - a[i - 1] > 1:
		if i % 2 == 1:
			t = max(t, b[i] - 1 + a[n + 1] - a[i] - (b[n + 1] - b[i]))
		else:
			t = max(t, b[i - 1] + a[i] - a[i - 1] - 1 + a[n + 1] - a[i] - (b[n + 1] - b[i]))
print(t)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.insert(0, 0)
a.append(m)
n += 2
prev = [0] * n
for i in range(1, n, 2):
	prev[i] = a[i] - a[i - 1]
for i in range(1, n):
	prev[i] = prev[i - 1] + prev[i]
flip = [0] * n
for i in range(1, n):
	j = n - 1 - i
	if j % 2 != 0:
		flip[j] = a[j + 1] - a[j]
for i in range(1, n):
	j = n - 1 - i
	flip[j] = flip[j] + flip[j + 1]
print(max(prev[-1], max((prev[i] + flip[i + 1] + abs(a[i + 1] - a[i] - 1) for i in range(n - 1)))))


(n, M) = map(int, input().split())
pro = [int(x) for x in input().split()]
pro.append(M)
on = [0] * (n + 1)
off = [0] * (n + 1)
on[0] = pro[0]
for i in range(1, n + 1):
	if i % 2 != 0:
		on[i] = on[i - 1]
		off[i] = off[i - 1] + pro[i] - pro[i - 1]
	else:
		on[i] = on[i - 1] + pro[i] - pro[i - 1]
		off[i] = off[i - 1]
time = on[n]
new = on[0]
for i in range(1, n + 1):
	if i % 2 == 0 and pro[i] - pro[i - 1] > 1:
		new = on[i] + off[n] - off[i] - 1
	elif i % 2 != 0 and pro[i] - pro[i - 1] > 1:
		new = on[i - 1] + off[n] - off[i - 1] - 1
	if new > time:
		time = new
print(time)


(n, m) = map(int, input().strip().split())
l = list(map(int, input().strip().split()))
l.insert(0, 0)
l.append(m)
lc = []
lo = []
on = 0
off = 0
lo.append([0, 0])
for i in range(1, n + 2):
	if i % 2 == 1:
		on = on + l[i] - l[i - 1]
	else:
		off = off + l[i] - l[i - 1]
	lo.append([on, off])
max1 = on
lc.append([on, off])
for i in range(1, n + 2):
	if i % 2 == 1:
		on = on - l[i] + l[i - 1]
	else:
		off = off - l[i] + l[i - 1]
	lc.append([on, off])
for i in range(1, n + 2):
	if i % 1 == 0 and l[i] - l[i - 1] > 1:
		curron = lo[i - 1][0] + l[i] - l[i - 1] - 1 + lc[i][1]
		if curron > max1:
			max1 = curron
	elif l[i] - l[i - 1] > 1:
		curron = lo[i - 1][0] + l[i] - 1 - l[i - 1] + lc[i][1]
		if curron > max1:
			max1 = curron
	else:
		continue
print(max1)


(n, m) = input().strip().split()
(n, m) = (int(n), int(m))
a = [0] + [int(_) for _ in input().strip().split()] + [m]
temp = 1
b = [0] * len(a)
for i in range(len(a)):
	b[i] = temp
	temp = 1 - temp
b[len(a) - 1] = 0
original_time = 0
for i in range(len(a)):
	if b[i] == 0 and b[i - 1] == 1:
		original_time += a[i] - a[i - 1]
right_time = 0
left_time = original_time
ans = original_time
for i in range(len(a) - 1, 0, -1):
	if b[i - 1] == 0:
		if a[i] - a[i - 1] > 1:
			right_time += a[i] - a[i - 1] - 1
			ans = max(ans, left_time + right_time)
			right_time += 1
		else:
			right_time += 1
	elif b[i - 1] == 1:
		left_time -= a[i] - a[i - 1]
print(ans)


(n, M) = [int(x) for x in input().split()]
l = [0] + [int(x) for x in input().split()] + [M]
s_on = 0
x_on = 0
for i in range(1, len(l), 2):
	s_on += l[i] - l[i - 1]
ok = s_on
for i in range(2, len(l), 2):
	x_on += l[i - 1] - l[i - 2]
	if l[i] - l[i - 1] > 1:
		t = s_on - x_on
		ok = max(ok, x_on + M - l[i - 1] - t - 1)
print(ok)


(n, M) = map(int, input().split())
s = [0] + list(map(int, input().split())) + [M]
alist = [s[i] - s[i - 1] for i in range(1, n + 2)]
litall = alist[::2]
unlitall = alist[1::2]
t = sum(litall)
lit = 0
unlit = sum(unlitall)
if set(alist) == {1}:
	print(t)
else:
	for i in range(n + 1):
		if i % 2 == 1:
			m = i // 2
			lit += litall[m]
			unlit -= unlitall[m]
		ans = lit + unlit + alist[i] - 1
		if ans > t:
			t = ans
	print(t)


(n, M) = map(int, input().split())
list = input().split()
list = [int(x) for x in list]
list.append(0)
list.append(M)
list.sort()
onesum = []
anothersum = []
time = []
for i in range(1, n + 2, 2):
	onesum.append(list[i] - list[i - 1])
	if i < n + 1:
		anothersum.append(list[i + 1] - list[i])
nochange = sum(onesum)
if len(onesum) == len(anothersum):
	timetry = nochange - 1 + anothersum[-1]
	time.append(timetry)
	for i in range(1, len(onesum)):
		timetry = timetry - onesum[-i] + anothersum[-(i + 1)]
		time.append(timetry)
else:
	timetry = nochange - onesum[-1] - 1 + anothersum[-1]
	time.append(timetry)
	for i in range(1, len(anothersum)):
		timetry = timetry - onesum[-(i + 1)] + anothersum[-(i + 1)]
		time.append(timetry)
time.append(nochange)
print(max(time))


(n, m) = map(int, input().split())
a = list(map(int, input().split())) + [m, 0]
left_on = [0] * (n + 2)
right_off = [0] * (n + 2)
status = 1
for i in range(n + 1):
	if status == 1:
		left_on[i] = left_on[i - 1] + a[i] - a[i - 1]
	else:
		left_on[i] = left_on[i - 1]
	status = 1 - status
status = 1 - status
for i in range(n - 1, -1, -1):
	if status == 1:
		right_off[i] = right_off[i + 1]
	else:
		right_off[i] = right_off[i + 1] + a[i + 1] - a[i]
	status = 1 - status
ans = left_on[n]
status = 1
for i in range(n + 1):
	if a[i] - a[i - 1] != 1:
		if status == 1:
			ans = max(ans, left_on[i] - 1 + right_off[i])
		else:
			ans = max(ans, left_on[i] + a[i] - a[i - 1] - 1 + right_off[i])
	status = 1 - status
print(ans)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l = [0] + l + [m]
n += 2
even = [0]
odd = [0]
for i in range(1, n, 2):
	even.append(l[i] - l[i - 1])
for i in range(2, n, 2):
	odd.append(l[i] - l[i - 1])
for i in range(1, len(even)):
	even[i] = even[i] + even[i - 1]
for i in range(1, len(odd)):
	odd[i] = odd[i] + odd[i - 1]
mx = max(even[-1], odd[-1])
for i in range(1, len(even)):
	mx = max(mx, even[i] + odd[-1] - odd[i - 1] - 1)
print(mx)


(n, m) = list(map(int, input().split()))
a = [0] + list(map(int, input().split())) + [m]
distances = []
(maxOn, maxOff) = (0, 0)
for i in range(1, n + 2):
	dist = a[i] - a[i - 1]
	distances.append(dist)
	if i % 2 == 1:
		maxOn += dist
	else:
		maxOff += dist
optimalOn = maxOn
tempOff = maxOff
tempOn = maxOn
for i in range(n + 1):
	di = distances[i]
	diff = di - 1
	if i % 2 == 0:
		if di > 1:
			optimalOn = max(optimalOn, maxOn + tempOff - tempOn + diff)
		tempOn -= di
	else:
		if di > 1:
			optimalOn = max(optimalOn, maxOn + tempOff - tempOn - 1)
		tempOff -= di
print(optimalOn)


(n, M) = map(int, input().split())
a = [int(x) for x in input().split()]
a.insert(0, 0)
a.append(M)
b = []
lindex = []
s = 0
for i in range(1, n + 2, 2):
	s = s + a[i] - a[i - 1]
	b.append(s)
	if i < n + 1 and a[i + 1] - a[i] > 1:
		lindex.append(i)
l0 = b[-1]
list3 = [l0]
for i in lindex:
	on = l0 - b[(i - 1) // 2]
	off = M - a[i] - on
	if off > on + 1:
		l1 = l0 + off - on - 1
		list3.append(l1)
print(max(list3))


(a, b) = [int(x) for x in input().split()]
ori = list(map(int, input().split()))
oi = ori[:]
s = [ori[0]]
for y in range(1, a):
	s.append(ori[y] - ori[y - 1])
s.append(b - ori[-1])
for x in range(1, a, 2):
	oi[x] = -oi[x]
time = sum(oi)
if time < 0:
	time += b
ot = time
f = 0
for q in range(a):
	p = s[q]
	if q > 0:
		f += oi[q - 1]
	if p > 1:
		l = 0
		if f < 0:
			ff = f - oi[q - 1]
		else:
			ff = f
		if q % 2:
			l = b - ori[q] - ot + ff
			time = max(time, ff + l + p - 1)
		else:
			l = b - ori[q] - ot + ff - p
			time = max(time, ff + l + p - 1)
if a % 2:
	time = max(time, ot + s[-1] - 1)
print(time)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
gar = []
shadow = []
gar.append(a[0])
light = False
a.append(m)
for i in range(1, n + 1):
	dl = a[i] - a[i - 1]
	if light:
		gar.append(dl)
		light = False
	else:
		shadow.append(dl)
		light = True
light = sum(gar)
dark = sum(shadow)
lightmax = light
teclight = 0
tecdark = 0
if n % 2 == 0:
	n = n // 2
else:
	n = n // 2 + 1
for i in range(n):
	if i != n - 1:
		teclight += gar[i]
		light -= gar[i]
		if gar[i] > 1:
			newlight = teclight - 1 + dark
			lightmax = max(lightmax, newlight)
		tecdark += shadow[i]
		dark -= shadow[i]
		if shadow[i] > 1:
			newlight = teclight + shadow[i] - 1 + dark
			lightmax = max(lightmax, newlight)
	elif len(shadow) == n:
		teclight += gar[i]
		light -= gar[i]
		if gar[i] > 1:
			newlight = teclight - 1 + dark
			lightmax = max(lightmax, newlight)
		tecdark += shadow[i]
		dark -= shadow[i]
		if shadow[i] > 1:
			newlight = teclight + shadow[i] - 1 + dark
			lightmax = max(lightmax, newlight)
print(lightmax)


(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [m]
b = [0] * (n + 2)
f = (-1) ** n
l = (a[n + 1] - a[n]) * f
ans = max(0, (a[n + 1] - a[n] - 1) * -f) if a[n + 1] - a[n] > 1 else 0
for i in range(n - 1, -1, -1):
	b[i] = b[i + 1] + (a[i + 2] - a[i + 1]) * -f
	if a[i + 1] - a[i] > 1:
		ans = max(ans, b[i] + a[i + 1] - a[i] - 1 if f == 1 else b[i] - 1)
	l += (a[i + 1] - a[i]) * -f
	f *= -1
print(ans + (l + m) // 2)


(n, M) = map(int, input().split())
a = [0]
a += list(map(int, input().split()))
a.append(M)
intervals = [0]
for i in range(1, len(a)):
	intervals.append(a[i] - a[i - 1])
intervalsodd = []
intervalseven = []
for i in range(1, len(intervals)):
	if i % 2 == 1:
		intervalsodd.append(intervals[i])
	else:
		intervalseven.append(intervals[i])
max = sum(intervalsodd)
if n % 2 == 1:
	i = 1
	T = sum(intervalsodd) + intervalseven[-i] - 1
	if T > max:
		max = T
	while i + 1 <= len(intervalseven):
		T = T - intervalsodd[-i] + intervalseven[-(i + 1)]
		if T > max:
			max = T
		i += 1
else:
	i = 1
	T = sum(intervalsodd) - intervalsodd[-i] + intervalseven[-i] - 1
	if T > max:
		max = T
	while i + 1 <= len(intervalseven):
		T = T - intervalsodd[-(i + 1)] + intervalseven[-(i + 1)]
		if T > max:
			max = T
		i += 1
print(max)


def main():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.append(m)
	arr.insert(0, 0)
	on_total = 0
	off_total = 0
	on = True
	for i in range(1, len(arr)):
		if on:
			on_total += arr[i] - arr[i - 1]
		else:
			off_total += arr[i] - arr[i - 1]
		on = not on
	on = False
	ans = on_total
	curr_on = 0
	curr_off = 0
	for i in range(1, len(arr)):
		on = not on
		if arr[i - 1] != arr[i] - 1:
			x = arr[i] - 1
			if on:
				ans = max(ans, curr_on + x - arr[i - 1] + off_total - curr_off)
			else:
				ans = max(ans, curr_on + 1 + off_total - curr_off - arr[i] + arr[i - 1])
			x = arr[i - 1] + 1
			if on:
				ans = max(ans, curr_on + x - arr[i - 1] + off_total - curr_off)
			else:
				ans = max(ans, curr_on + arr[i] - x + off_total - curr_off - arr[i] + arr[i - 1])
		if on:
			curr_on += arr[i] - arr[i - 1]
		else:
			curr_off += arr[i] - arr[i - 1]
	print(ans)
main()


(n, m) = map(int, input().split())
A = [0] + list(map(int, input().split())) + [m]
ans = 0
on = 0
ON = [0] * (n + 3)
for i in range(n, -1, -1):
	ON[i] = ON[i + 2] + A[i + 1] - A[i]
a = 0
b = 0
for i in range(n + 1):
	if A[i + 1] - A[i] >= 2:
		if i % 2 == 0:
			a = on + 1 + ON[i + 1]
			b = on + A[i + 1] - A[i] - 1 + ON[i + 1]
			ans = max(ans, a, b)
		else:
			a = on + A[i + 1] - A[i] - 1 + ON[i + 2]
			b = on + 1 + ON[i + 2]
			ans = max(ans, a, b)
	if i % 2 == 0:
		on += A[i + 1] - A[i]
ans = max(ON[0], ans)
print(ans)


(n, M) = map(int, input().split())
x = [0] + [int(i) for i in input().split()] + [M]
light = [x[i + 1] - x[i] for i in range(n + 1)]
oddLeft = [0]
preSum = [0]
for i in range(len(light)):
	if i % 2 == 0:
		oddLeft.append(oddLeft[-1] + light[i])
	else:
		oddLeft.append(oddLeft[-1])
	preSum.append(light[i] + preSum[-1])
res = max(oddLeft[-1], preSum[-1] - oddLeft[-1])
for i in range(len(light)):
	if light[i] > 1:
		res = max(res, oddLeft[i] + light[i] - 1 + preSum[-1] - preSum[i + 1] - (oddLeft[-1] - oddLeft[i + 1]))
print(res)


(n, M) = map(int, input().split())
data = list(map(int, input().split()))
state = False
states = [0 for i in range(n + 1)]
states[0] = (data[0], 0)
for i in range(1, n + 1):
	value = (M if i == n else data[i]) - data[i - 1]
	states[i] = (states[i - 1][0] + (value if state else 0), states[i - 1][1] + (0 if state else value))
	state = not state
ans = states[n][0]
for i in range(n + 1):
	if (M if i == n else data[i]) - (data[i - 1] if i > 0 else 0) > 1:
		val = 0
		if i != 0 and i != n:
			val = states[i - 1][0] + states[n][1] - states[i][1]
			val += data[i] - data[i - 1] - 1
		if i == 0:
			val = states[n][1]
			val += data[0] - 1
		if i == n:
			val = states[n - 1][0]
			val += M - data[n - 1] - 1
		ans = max(ans, val)
print(ans)


(a, b) = map(int, input().split())
lt = [0] + [int(i) for i in input().split()] + [b]
(lton, ltoff) = ([0], [0] * (2 - a % 2))
for i in range(1, a + 2, 2):
	lton += [lton[(i + 1) // 2 - 1] + lt[i] - lt[i - 1]]
for i in range(a + 2 - 1 + a % 2, 1, -2):
	ltoff += [ltoff[(a + 2 - i) // 2 + 1 - a % 2] + lt[i - 1] - lt[i - 2]]
m = lton[-1]
for i in range(1, a + 2):
	if lt[i] - 1 == lt[i - 1]:
		pass
	elif i % 2:
		m = max(m, lt[i] - lt[i - 1] - 1 + lton[(i - 1) // 2] + ltoff[(a + 2 - i) // 2])
	else:
		m = max(m, lt[i] - lt[i - 1] - 1 + lton[i // 2] + ltoff[(a + 2 - i) // 2])
print(m)


def lit_time(t, s):
	lit = 0
	time0 = []
	for i in range(1, s, 2):
		lit += t[i] - t[i - 1]
		time0.append(lit)
	return time0
(n, M) = [int(x) for x in input().split()]
a = [0] + [int(x) for x in input().split()] + [M]
time = lit_time(a, n + 2)
solution = time[-1]
total = solution
for j in range(2, n + 2, 2):
	if a[j] - a[j - 2] != 2:
		l0 = time[j // 2 - 1]
		s1 = l0 + M - a[j - 1] - (total - l0) - 1
		solution = max([solution, s1])
print(solution)


(length, endTime) = map(int, input().split())
array = [0] + list(map(int, input().split())) + [endTime]
x = [(array[i + 1] - array[i]) * (-1) ** i for i in range(len(array) - 1)]
preSum = [x[0]]
for i in range(1, len(x)):
	if x[i] > 0:
		preSum.append(preSum[-1] + x[i])
	else:
		preSum.append(preSum[-1])
appSum = [0]
for i in range(len(x) - 1, -1, -1):
	if x[i] < 0:
		appSum.append(-x[i] + appSum[-1])
	else:
		appSum.append(appSum[-1])
appSum = list(reversed(appSum))
res = sum([i for i in x if i > 0])
for i in range(len(x) - 1, -1, -1):
	if x[i] < -1:
		res = max(res, preSum[i - 1] - x[i] - 1 + appSum[i + 1])
print(res)


(n, m) = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
a.append(m)
a.insert(0, 0)
n += 2
diff = [0] * (n - 1)
d = n - 2
for i in range(n - 1, 0, -1):
	diff[d] = a[i] - a[i - 1]
	if i < n - 2:
		diff[d] += diff[d + 2]
	d -= 1
ontime = diff[0]
for d in range(n - 1):
	if d % 2 == 0:
		prevontime = diff[0] - diff[d]
		afterofftime = 0
		if d < n - 2:
			afterofftime += diff[d + 1]
		ontime = max(ontime, prevontime + afterofftime + a[d + 1] - a[d] - 1)
	else:
		if a[d] + 1 == a[d + 1]:
			continue
		prevontime = diff[0]
		if d < n - 2:
			prevontime -= diff[d + 1]
		afterofftime = 0
		if d < n - 3:
			afterofftime += diff[d + 2]
		ontime = max(ontime, prevontime + afterofftime + 1)
print(ontime)


(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [m]
on = []
for i in range(1, n + 2):
	if i % 2 == 1:
		on.append(a[i] - a[i - 1])
on_sum = sum(on)
on_max = on_sum
if n % 2 == 1:
	i = n + 1
else:
	i = n
	on_sum -= a[n + 1] - a[n]
while i > 0:
	if a[i] - a[i - 1] > 1:
		b = a[i - 1] + 1
		on_max = max(on_max, on_sum + a[i] - b)
	on_sum = on_sum + (a[i] - a[i - 1]) - (a[i - 1] - a[i - 2])
	if a[i - 1] - a[i - 2] > 1:
		b = a[i - 1] - 1
		on_max = max(on_max, on_sum + b - a[i - 2])
	i -= 2
print(on_max)


(a, b) = map(int, input().split())
l = [0] + [int(i) for i in input().split()] + [b]
l1 = []
for i in range(a + 1):
	l1.append(l[i + 1] - l[i])
even1 = 0
odd1 = 0
odd = even = c = d = 0
for i in range(a + 1):
	if i % 2 == 0:
		odd += l1[i]
	else:
		even += l1[i]
for i in range(0, 2):
	if i % 2 == 0:
		if l1[i] > 1:
			c = even + l1[i] - 1
	else:
		odd1 += l1[0]
		if l1[i] > 1:
			c = l1[0] + even - 1
d = max(c, d)
for i in range(2, a + 1):
	if i % 2 == 0:
		even1 += l1[i - 1]
		if l1[i] > 1:
			c = odd1 + even - even1 + l1[i] - 1
	else:
		odd1 += l1[i - 1]
		if l1[i] > 1:
			c = odd1 + even - even1 - 1
	d = max(c, d)
d = max(d, odd)
print(d)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = [a[0]]
for i in range(n):
	if i == n - 1:
		b.append(m - a[i])
	else:
		b.append(a[i + 1] - a[i])
l = n + 1
dict1 = {}
dict1 = dict1.fromkeys(range(l + 1), True)
c = [0] * l
x = 0
for k in range(0, l, 2):
	x += b[k]
	if b[k] == 1:
		dict1[k] = False
c.append(x)
for j in range(0, l, 2):
	if j == 0:
		cn = m - x + b[0] - 1
	else:
		cn += b[j] - b[j - 1]
	c[j] = cn
for j in range(1, l, 2):
	if j == 1:
		cn = m - x + b[0] - 1
	else:
		cn += b[j - 1] - b[j - 2]
	c[j] = cn
d = []
for s in range(l + 1):
	if dict1[s]:
		d.append(c[s])
print(max(d))


(n, m) = map(int, input().split())
a = [0]
for x in input().split():
	a.append(int(x))
prev = m
pos = 0
neg = 0
on = n % 2 == 0
best_diff = 0
for i in range(n, -1, -1):
	if not on:
		diff = neg + prev - a[i] - 1 - pos
		best_diff = max(diff, best_diff)
		neg += prev - a[i]
	else:
		pos += prev - a[i]
	on = not on
	prev = a[i]
print(pos + best_diff)


(n, M) = [int(x) for x in input().split()]
l = [0] + [int(x) for x in input().split()] + [M]
maximum = 0
b = [0] * (n + 2)
for x in range(0, n // 2 + 1):
	b[2 * x] = b[2 * x - 1]
	y = l[2 * x + 1] - l[2 * x]
	b[2 * x + 1] = b[2 * x] + y
	maximum += y
if n % 2 == 1:
	b[-1] = b[-2]
for x in range(n + 1):
	if l[x + 1] - l[x] > 1:
		if x % 2 == 0:
			maximum = max(maximum, 2 * b[x + 1] - 1 + M - l[x + 1] - b[-1])
		else:
			maximum = max(maximum, 2 * b[x + 1] + M - 1 - l[x] - b[-1])
print(maximum)


(n, m) = map(int, input().split())
li = list(map(int, input().split()))
mod = [0]
for i in range(n):
	mod.append(li[i])
mod.append(m)
on_time = [0] * (n + 2)
off_time = [0] * (n + 2)
for i in range(1, n + 2):
	if i % 2 == 0:
		on_time[i] = on_time[i - 1]
	else:
		on_time[i] = mod[i] - mod[i - 1] + on_time[i - 1]
	off_time[i] = mod[i] - on_time[i]
ans = on_time[-1]
for i in range(1, n + 2):
	if mod[i] - mod[i - 1] > 1:
		temp = on_time[i - 1] + (mod[i] - mod[i - 1] - 1) + off_time[-1] - off_time[i]
		ans = max(temp, ans)
print(ans)


(n, M) = map(int, input().split())
A = [int(x) for x in input().split()]
odd = []
even = []
B = [A[0]]
for i in range(1, n):
	B.append(A[i] - A[i - 1])
B.append(M - A[-1])
import math
for i in range(math.ceil(n / 2)):
	odd.append(B[2 * i])
	even.append(B[2 * i + 1])
if n % 2 == 0:
	odd.append(B[n])
answer = sum(odd)
p = 0
q = sum(even)
for i in range(math.ceil(n / 2)):
	p = p + odd[i]
	if i != 0:
		q = q - even[i - 1]
	s = p + q - 1
	if s > answer:
		answer = s
print(answer)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
arr = [0] + list(map(int, input().split())) + [m]
ans = 0
left = [(0, False) for _ in range(n + 2)]
right = [(0, False) for _ in range(n + 2)]
for i in range(1, len(arr)):
	if i % 2 == 0:
		left[i] = (left[i - 1][0], False)
	else:
		left[i] = (left[i - 1][0] + arr[i] - arr[i - 1], True)
start_immediately = False
if len(arr) % 2 == 1:
	start_immediately = True
for i in range(len(arr) - 2, -1, -1):
	if start_immediately:
		right[i] = (right[i + 1][0] + arr[i + 1] - arr[i], True)
		start_immediately = False
	else:
		right[i] = (right[i + 1][0], False)
		start_immediately = True
ans = left[-1][0]
for i in range(len(arr)):
	if i != 0 and arr[i] - 1 != arr[i - 1]:
		if left[i][1]:
			ans = max(ans, left[i][0] + right[i][0] - 1)
		else:
			ans = max(ans, left[i][0] + right[i][0] + 1)
	if i != len(arr) - 1 and arr[i] + 1 != arr[i + 1]:
		if right[i][1]:
			ans = max(ans, left[i][0] + right[i][0] - 1)
		else:
			ans = max(ans, left[i][0] + right[i][0])
print(ans)


f = lambda : map(int, input().split())
(n, m) = f()
a = list(f())
a = [0] + a + [m]
(time_int, light, dark) = ([], 0, 0)
for i in range(len(a) - 1):
	t = a[i + 1] - a[i]
	time_int.append(t)
	if i % 2 == 0:
		light += t
	else:
		dark += t
left_light = 0
for i in range(len(time_int)):
	if i % 2 != 0:
		dark -= time_int[i]
	if left_light + dark + time_int[i] - 1 > light:
		light = left_light + dark + time_int[i] - 1
	if i % 2 == 0:
		left_light += time_int[i]
print(light)


(n, m) = map(int, input().split())
li = [int(x) for x in input().split()]
li.append(m)
lit0 = 0
for i in range(0, n + (n + 1) % 2):
	lit0 += (-1) ** i * li[i]
lit = m - lit0 + li[0] - 1
ma = max(lit0, lit)
for i in range(0, n - 1, 2):
	lit = lit + li[i + 2] - 2 * li[i + 1] + li[i]
	if lit > ma:
		ma = lit
print(ma)


(n, m) = map(int, input().split())
l = [[0 for i in range(4)] for j in range(10 ** 5 + 5)]
a = [int(i) for i in input().split()]
l[0][0] = a[0]
d = 1
for i in range(1, n):
	l[i][d] = a[i] - a[i - 1]
	d = int(not d)
l[n][d] = m - a[n - 1]
for i in range(n - 1, -1, -1):
	l[i][2] = l[i + 1][2] + l[i + 1][0]
	l[i][3] = l[i + 1][3] + l[i + 1][1]
ans = l[0][2] + l[0][0]
for i in range(n + 1):
	if l[i][0] > 0:
		ans = max(ans, l[0][2] + l[0][0] - 1 + l[i][3] - l[i][2])
	else:
		ans = max(ans, l[0][2] + l[0][0] + l[i][1] - 1 - l[i][2] + l[i][3])
print(ans)


(n, m) = [int(x) for x in list(input().split())]
a = list([int(x) for x in list(input().split())])
a.append(m)
diff = [a[0]]
s = 0
sure = 0
for i in range(1, n + 1):
	diff.append(a[i] - a[i - 1])
a = diff
for i in range(0, len(a), 2):
	s = s + a[i]
ans = s
nm = m
for i in range(0, len(a), 2):
	lit = s - a[i] - sure
	temp = sure + a[i] - 1 + nm - a[i] - lit
	if a[i] > 1:
		ans = max(ans, temp)
	if i < len(a) - 1 and a[i + 1] > 1:
		ans = max(ans, temp)
	sure += a[i]
	nm = nm - a[i]
	if i < len(a) - 1:
		nm = nm - a[i + 1]
print(ans)


(n, m) = [int(x) for x in input().split()]
s = [int(x) for x in input().split()]
s.insert(0, 0)
l = []
if n == 1:
	print(m - 1)
elif n % 2 == 0:
	t = m - s[n]
	for i in range(n, 0, -2):
		q = -t + s[i] - s[i - 1]
		t = t - s[i] + 2 * s[i - 1] - s[i - 2]
		l.append(q)
	mega = max(l)
	origin = (t + m) // 2
	if mega > 1:
		print(mega + origin - 1)
	else:
		print(origin)
else:
	t = m - s[n]
	l.append(t)
	for i in range(n, 2, -2):
		q = -t + s[i] - s[i - 1]
		t = t - s[i] + 2 * s[i - 1] - s[i - 2]
		l.append(t)
	q = -t + s[1] - s[0]
	mega = max(l)
	origin = (q + m) // 2
	if mega > 1:
		print(mega + origin - 1)
	else:
		print(origin)


[count, length] = [int(i) for i in input().split(' ')]
size = []
odd_total = even_total = 0
temp = index = 0
input_nums = input().split(' ')
input_nums.append(length)
for i in input_nums:
	now_input = int(i)
	now_input -= temp
	size.append(now_input)
	if index % 2 == 0:
		even_total += now_input
	else:
		odd_total += now_input
	temp += now_input
	index += 1
odd_remain = odd_total
even_sum = 0
result = even_total
for i in range(0, count + 1):
	now = size[i]
	if i % 2 == 1:
		odd_remain -= now
	new_result = even_sum + odd_remain + now - 1
	if new_result > result:
		result = new_result
	if i % 2 == 0:
		even_sum += now
print(result)


from itertools import accumulate
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
s = set(a + [0, m, m + 1])
on_starts = [0] + a[1::2]
off_starts = a[::2] + [m]
if len(on_starts) < len(off_starts):
	on_starts.append(m)
segs = [y - x for (x, y) in zip(on_starts, off_starts)]
acc = list(accumulate(segs))
best = acc[-1]
for (i, off_start) in enumerate(off_starts):
	if off_start - 1 not in s:
		cur = acc[i] - 1
		cur += m - off_start - (acc[-1] - acc[i])
		best = max(best, cur)
	if off_start + 1 not in s:
		cur = acc[i] - 1
		cur += m - off_start - (acc[-1] - acc[i])
		best = max(best, cur)
print(best)


(n, M) = map(int, input().split(' '))
a = [0] + list(map(int, input().split(' '))) + [M]
before = [0]
after = []
op = 1
be = 0
af = 0
out = []
ou = 0
for h in range(0, n + 1):
	ou -= (-1) ** h * a[h]
if n % 2 == 0:
	ou += M
after.append(ou)
out.append(ou)
for i in range(1, n + 2):
	m = 0
	be = before[i - 1] + op * (a[i] - a[i - 1])
	af = after[i - 1] - op * (a[i] - a[i - 1])
	before.append(be)
	after.append(af)
	op = 1 - op
for j in range(0, n + 2):
	ou = before[j] + (M - a[j] - after[j]) - 1
	out.append(ou)
print(max(out))


(n, m) = map(int, input().split())
l = [*map(int, '0 {} {}'.format(input(), m).split())]
s = [l[i + 1] - l[i] for i in range(len(l) - 1)]
t = sum(s[1::2]) + s[0] - 1
r = max((sum(s[::2]), t))
for i in range(2, len(s), 2):
	t = t - s[i - 1] + s[i]
	if t > r:
		r = t
print(r)


[n, M] = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a.insert(0, 0)
s = 0
i = 1
S = [0]
if len(a) % 2 == 1:
	a.append(M)
	n = len(a)
	for i in range(1, n, 2):
		s = s + a[i] - a[i - 1]
		S.append(s)
		i = i + 2
else:
	n = len(a)
	for i in range(1, n, 2):
		s = s + a[i] - a[i - 1]
		S.append(s)
		i = i + 2
	a.append(M)
n = len(a)
sn = 0
for i in range(1, n):
	if i % 2 == 1 and a[i] - 1 != a[i - 1]:
		sn = S[int(i // 2)] - (S[-1] - S[int(i // 2) + 1] - M + a[i]) + a[i] - 1 - a[i - 1]
	elif i % 2 == 0 and a[i - 1] + 1 != a[i]:
		sn = S[int(i // 2)] - (S[-1] - S[int(i // 2)] - M) - a[i - 1] - 1
	else:
		sn = 0
	s = max(s, sn)
print(s)


def main():
	(n, M) = list(map(int, input().split()))
	seq = [0] + list(map(int, input().split())) + [M]
	seq = [seq[i + 1] - seq[i] for i in range(n + 1)]
	ret = [sum([seq[i] for i in range(n + 1) if i % 2 == 0])]
	seq = [seq[i] * (-1) ** i for i in range(n + 1)]
	s = 0
	s0 = sum(seq)
	for i in range(n + 1):
		ret.append(-1 + (s - s0 + M) // 2)
		a = seq[i]
		s += a
		s0 -= a
	print(max(ret))
	return 0
main()


from itertools import accumulate
(n, m) = list(map(int, input().split()))
tt = n // 2 + 1
moments = [0] + list(map(int, input().split())) + [m]
times = [moments[i] - moments[i - 1] for i in range(1, n + 2)]
light = times[::2]
dark = times[1::2]
light_time = list(accumulate(light))
dark_time = [0] + list(accumulate(dark))
res = light_time[-1]
for i in range(tt):
	if times[2 * i] > 1:
		res = max(res, light_time[i] - 1 + (dark_time[-1] - dark_time[i]))
	if i == 0 or times[2 * i - 1] > 1:
		res = max(res, light_time[i] + dark_time[-1] - dark_time[i] - 1)
print(res)


(n, M) = map(int, input().split())
s = list(map(int, input().split()))
s.append(0)
s.append(M)
s.sort()
x = 0
first = 0
for i in range(0, n + 1, 2):
	first += s[i + 1] - s[i]
lst = []
lst.append(first)
for j in range(1, n + 1, 2):
	f = 0
	x += s[j] - s[j - 1]
	if s[j + 1] - 1 > s[j]:
		t = first - x
		f = x + (s[j + 1] - s[j] - 1) + (M - s[j + 1] - t)
		lst.append(f)
print(max(lst))


(n, M) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [M]
gap = []
for i in range(1, len(a)):
	gap.append(a[i] - a[i - 1])
maxi = 0
for m in range(0, len(gap), 2):
	maxi += gap[m]
light = [0, gap[0]]
dark = [M - maxi, M - maxi - gap[1]]
for g in range(2, len(gap)):
	if g % 2 == 0:
		light.append(light[g - 2] + gap[g - 2])
		dark.append(dark[g - 2] - gap[g - 1])
	else:
		light.append(light[g - 1] + gap[g - 1])
		dark.append(dark[g - 1] - gap[g])
b = [maxi]
for l in range(len(gap)):
	b.append(light[l] + dark[l] + gap[l] - 1)
print(max(b))


(N, M) = map(int, input().split())
light = [0] + [int(_) for _ in input().split()] + [M]
sumlist = []
(sumlight, ans) = (0, -10 ** 30)
for i in range(N + 1):
	sumlight += (-1) ** (i + 1) * light[i]
	sumlist.append(sumlight)
for i in range(1, N + 1):
	if light[i] > light[i - 1] + 1:
		ans = max(ans, 2 * sumlist[i - 1] - sumlight + (-1) ** (i + 1) * (light[i] - 1))
	if light[i] < light[i + 1] - 1:
		ans = max(ans, 2 * sumlist[i] - sumlight + (-1) ** i * (light[i] + 1))
if N % 2 == 0:
	print(max(ans, sumlight + M))
else:
	print(max(ans + M, sumlight))


def solve(N, M, A):
	A = [0] + A + [M]
	D = [A[i + 1] - A[i] for i in range(N + 1)]
	LD = len(D)
	evensum = 0
	oddsum = 0
	for i in range(LD):
		if i % 2 == 0:
			evensum += D[i]
		else:
			oddsum += D[i]
	best = evensum
	accum = 0
	for i in range(LD):
		d = D[i]
		if i % 2 == 0:
			evensum -= d
			if d > 1:
				best = max(best, accum + d - 1 + oddsum)
			accum += d
		else:
			oddsum -= d
			if d > 1:
				best = max(best, accum + d - 1 + oddsum)
	return best

def main():
	(N, M) = [int(e) for e in input().split(' ')]
	A = [int(e) for e in input().split(' ')]
	assert len(A) == N
	print(solve(N, M, A))
main()


(n, m) = [int(x) for x in input().split()]
b = [0] + [int(x) for x in input().split()] + [m]
t = [0] + [b[1] - b[0]]
i = 2
j = 1
while i + 1 <= n + 1:
	t.append(t[j] + b[i + 1] - b[i])
	i += 2
	j += 1
light = t[-1]
for k in range(n + 1):
	if b[k + 1] - b[k] > 1:
		if k % 2 == 0:
			a = int(k / 2 + 1)
			light = max(light, t[a] - 1 + m - b[k + 1] - t[-1] + t[a])
		else:
			a = int((k + 1) / 2)
			light = max(light, t[a] - b[k] - 1 + m - t[-1] + t[a])
print(light)


(n, duration) = list(map(int, input().split(' ')))
flips = [0]
flips += list(map(int, input().split(' ')))
flips.append(duration)
posi_intervals = []
counter_intervals = [0] * (n + 1)
temp_sum = 0
counter_sum = 0
last_on = False
if n % 2 == 0:
	last_on = True
for i in range(1, n + 2):
	if i % 2 != 0:
		temp_sum += flips[i] - flips[i - 1]
	posi_intervals.append(temp_sum)
	j = n + 1 - i
	if last_on is False:
		if j % 2 != 0:
			counter_sum += flips[j + 1] - flips[j]
		counter_intervals[j] = counter_sum
	if last_on is True:
		if j % 2 != 0:
			counter_sum += flips[j + 1] - flips[j]
		counter_intervals[j] = counter_sum
for i in range(n + 1):
	temp = 0
	if i == 0:
		temp = flips[1] - 1 + counter_intervals[1]
	elif i < n and flips[i + 1] - flips[i] != 1:
		temp = posi_intervals[i - 1] + flips[i + 1] - flips[i] - 1 + counter_intervals[i + 1]
	else:
		temp = posi_intervals[i - 1] + flips[i + 1] - flips[i] - 1
	if temp > temp_sum:
		temp_sum = temp
print(temp_sum)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
a = [0] + a
a.append(m)
b1 = [0] * (n + 2)
b2 = [0] * (n + 2)
for i in range(1, n + 2):
	if i % 2 == 1:
		b1[i] = b1[i - 1] + a[i] - a[i - 1]
		b2[i] = b2[i - 1]
	else:
		b2[i] = b2[i - 1] + a[i] - a[i - 1]
		b1[i] = b1[i - 1]
res = b1[-1]
for i in range(1, n + 2):
	if a[i] - a[i - 1] > 1:
		if i % 2 == 1:
			res = max(res, b1[i] - 1 + b2[-1] - b2[i])
		else:
			res = max(res, b1[i] + b2[-1] - b2[i - 1] - 1)
print(res)


(n, M) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [M]
b = [0]
c = [0]
s = 0
p = 0
for i in range(1, len(a)):
	if i % 2 == 0:
		s += a[i] - a[i - 1]
		b.append(s)
	else:
		p += a[i] - a[i - 1]
		c.append(p)
m = len(b)
s = 0
for i in range(1, len(a)):
	if i % 2 == 1:
		s += a[i] - a[i - 1]
k = 0
for i in range(len(a) - 1):
	if i % 2 == 0:
		if a[i + 1] - a[i] > 1:
			s = max(s, c[i // 2] + a[i + 1] - 1 - a[i] + b[m - 1] - b[i // 2])
	else:
		k += 1
		if a[i + 1] - a[i] > 1:
			s = max(s, c[k] + a[i + 1] - a[i] - 1 + b[m - 1] - b[(i + 1) // 2])
print(s)


def solve(lights):
	(svieti, nesvieti) = ([0], [0])
	zapnuta = True
	for i in range(1, len(lights)):
		if zapnuta:
			svieti.append(svieti[i - 1] + lights[i] - lights[i - 1])
			nesvieti.append(nesvieti[i - 1])
		else:
			nesvieti.append(nesvieti[i - 1] + lights[i] - lights[i - 1])
			svieti.append(svieti[i - 1])
		zapnuta = not zapnuta
	zhasnute = nesvieti[-1]
	yield svieti[-1]
	if lights[1] != 1:
		yield (zhasnute - 1)
	for i in range(1, len(svieti) - 1):
		if lights[i] + 1 != lights[i + 1]:
			yield (svieti[i] + zhasnute - nesvieti[i] - 1)
		if lights[i] - 1 != lights[i - 1]:
			if svieti[i] == svieti[i - 1]:
				yield (svieti[i] + 1 + zhasnute - nesvieti[i])
			else:
				yield (svieti[i] - 1 + zhasnute - nesvieti[i])
	if lights[-1] - 1 != lights[-2]:
		if svieti[-1] == svieti[-2]:
			yield (svieti[-1] + 1 + zhasnute - zhasnute)
		else:
			yield (svieti[-1] + zhasnute - zhasnute)
(_, M) = map(int, input().split())
lights = [0] + list(map(int, input().split())) + [M]
print(max(solve(lights)))


(n, M) = [int(x) for x in input().split()]
l = [0]
l.extend([int(x) for x in input().split()])
t = 0
Max = 0
for i in range(n):
	Increment = (1 - 2 * (i % 2)) * (l[i + 1] - l[i])
	if Increment < -1:
		Max = max(Max, t - 1)
	t += Increment
	if Increment > 1:
		Max = max(Max, t - 1)
t += (1 - 2 * (n % 2)) * (M - l[n])
Max = max(Max, t)
print(Max + (M - t) // 2)


(n, m) = [int(x) for x in input().split()]
check = [0] + [int(x) for x in input().split()] + [m]
rec = [0] * (n + 1)
maxx = 0
for ite in range(1, n + 1):
	tmp = (-1) ** (ite - 1) * check[ite]
	maxx += tmp
	rec[ite] = maxx
maxx += (1 - n % 2) * m
for button in range(n + 1):
	if check[button + 1] - check[button] == 1:
		continue
	tmp = rec[button] - (rec[n] - rec[button]) + n % 2 * m
	if button % 2 == 0:
		maxx = max(maxx, check[button + 1] - 1 + tmp)
	else:
		maxx = max(maxx, -1 * (check[button] + 1) + tmp)
print(maxx)


(n, m) = map(int, input().split())
l = [int(x) for x in input().split()]
j = 0
b = [0] * (n + 1)
b[0] = l[0]
for i in range(0, n - 1):
	b[i + 1] = b[i] + (-1 + 2 * (i % 2)) * (l[i + 1] - l[i])
b[-1] = b[n - 1] + (1 - 2 * (n % 2)) * (m - l[-1])
print(max((b[-1] + m) // 2, (m + 2 * max(b) - b[-1] - 1) // 2))


(n, m) = map(int, input().split())
a = [0 for i in range(n + 2)]
a[1:-1] = map(int, input().split())
a[-1] = m
suf = [0 for i in range(n + 2)]
for i in range(n, -1, -1):
	if i % 2 == 0:
		suf[i] = suf[i + 1] + a[i + 1] - a[i]
	else:
		suf[i] = suf[i + 1]
ans = suf[0]
total = suf[0]
for i in range(0, n + 1):
	if a[i + 1] - a[i] > 1:
		if i % 2 == 0:
			ans = max(ans, total - suf[i] + 1 + (m - a[i] - suf[i]))
		else:
			ans = max(ans, total - suf[i] + (m - a[i] - suf[i] - 1))
print(ans)


(n, M) = map(int, input().split(' '))
aa = [0] + list(map(int, input().split(' '))) + [M]
ps = [0] * (len(aa) + 1)
ss = [0] * (len(aa) + 1)
en = True
for i in range(1, len(aa)):
	ps[i + 1] = ps[i] + (aa[i] - aa[i - 1] if en else 0)
	en = not en
for i in range(1, len(aa)):
	pos = len(aa) - 1 - i
	ss[i + 1] = ss[i] + (aa[pos + 1] - aa[pos] if en else 0)
	en = not en
res = ps[-1]
for i in range(0, len(aa) - 1):
	if aa[i + 1] - aa[i] >= 2:
		cur = ps[i + 1] + ss[len(aa) - (i + 1)] + (aa[i + 1] - aa[i] - 1)
		res = max(res, cur)
print(res)


(n, M) = map(int, input().split())
a = list(map(int, input().split()))
totalOn = 0
totalOff = 0
if n % 2 == 0:
	for i in range(0, n, 2):
		totalOn += a[i] - (a[i - 1] if i != 0 else 0)
	totalOn += M - a[-1]
	totalOff = M - totalOn
else:
	for i in range(0, n, 2):
		totalOn += a[i] - (a[i - 1] if i != 0 else 0)
	totalOff = M - totalOn
nTotalOn = 0
nTotalOff = 0
maxGain = 0
for i in range(0, n, 2):
	nTotalOn += a[i] - (a[i - 1] if i != 0 else 0)
	temp = (a[i + 1] if i != n - 1 else M) - a[i]
	nTotalOff += temp
	if temp > 1:
		leftOn = totalOn - nTotalOn
		leftOff = totalOff - nTotalOff
		gain = temp - 1 + leftOff - leftOn
		maxGain = maxGain if maxGain >= gain else gain
print(maxGain + totalOn)


(n, m) = map(int, input().split())
program = [int(x) for x in input().split()]
program.append(m)
if n % 2 != 0:
	program.append(m)
M = sum((program[i] * (-1) ** i for i in range(0, n + 1 + (n % 2 != 0))))
M_1 = M - 1
for j in range(n - (n % 2 == 0) - 1, -1, -2):
	M_1 = M_1 - program[j] + 2 * program[j + 1] - program[j + 2]
	M = max(M, M_1)
print(M)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = [[abs(0 - a[0]), 0]]
li = b[0][0]
off = 0
for i in range(n - 1):
	if i % 2 == 0:
		b.append([li, off + abs(a[i] - a[i + 1])])
		off += abs(a[i] - a[i + 1])
	else:
		b.append([li + abs(a[i] - a[i + 1]), off])
		li += abs(a[i] - a[i + 1])
if n % 2 == 0:
	b.append([li + abs(m - a[-1]), off])
else:
	b.append([li, off + abs(m - a[-1])])
ma = b[-1][0]
for i in range(1, len(b)):
	ma = max(ma, b[i][1] - b[i - 1][1] - 1 + b[i][0] + b[-1][1] - b[i][1])
print(ma)


(n, m) = map(int, input().split())
A = [-1, 0] + [int(x) for x in input().split()] + [m, m + 1]
S = 0
for i in range(1, len(A) - 2, 2):
	S += A[i + 1] - A[i]
best = S
pre = 0
up = True
for i in range(1, len(A) - 2, 1):
	if up:
		if A[i - 1] + 1 != A[i]:
			remaining = m - A[i] + 1
			remaining_ful = S - pre
			best = max([best, pre + (remaining - remaining_ful)])
		if A[i] + 1 != A[i + 1]:
			remaining = m - A[i] - 1
			remaining_ful = S - pre - 1
			best = max([best, pre + (remaining - remaining_ful) + 1])
	else:
		pre += A[i] - A[i - 1]
		if A[i - 1] + 1 != A[i]:
			remaining = m - A[i] + 1
			remaining_ful = S - pre + 1
			best = max([best, pre + (remaining - remaining_ful) - 1])
		if A[i] + 1 != A[i + 1]:
			remaining = m - A[i] - 1
			remaining_ful = S - pre
			best = max([best, pre + (remaining - remaining_ful)])
	up = not up
print(best)


(n, M) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
if n > 3:
	on = [a[0]]
	off = []
	b = a[0]
	c = 0
	for i in range(0, n - 2, 2):
		b += a[i + 2] - a[i + 1]
		c += a[i + 1] - a[i]
		on.append(b)
		off.append(c)
	if n % 2 == 1:
		c += M - a[-1]
		off.append(c)
	else:
		b += M - a[-1]
		c += a[-1] - a[-2]
		on.append(b)
		off.append(c)
	s = int()
	t = on[-1]
	for i in range(2, n - 1, 2):
		if a[i + 1] - a[i] > 1:
			s = on[int(i / 2)] + off[-1] - off[int(i / 2)] + a[i + 1] - a[i] - 1
			t = max(s, t)
	for i in range(3, n - 1, 2):
		if a[i + 1] - a[i] > 1:
			s = on[int((i - 1) / 2)] + M - on[-1] - off[int((i - 1) / 2)] + a[i + 1] - a[i] - 1
			t = max(s, t)
	if a[0] > 1:
		s = off[-1] + a[0] - 1
		t = max(s, t)
	if a[1] - a[0] > 1:
		s = a[0] - 1 + off[-1]
		t = max(s, t)
	if a[2] - a[1] > 1:
		s = a[0] + off[-1] - 1
		t = max(s, t)
	if n % 2 == 1 and M - a[-1] > 1:
		s = on[-1] + M - a[-1] - 1
		t = max(s, t)
	print(t)
elif n == 1:
	print(M - 1)
else:
	s = 0
	for i in range(n):
		s += a[i] * (-1) ** i
	if n % 2 == 0:
		s += M
	if M - a[-1] > 3:
		for i in range(min(M - 2, a[-1] + 1)):
			if i + 1 not in a:
				a.append(i + 1)
				b = sorted(a)
				si = 0
				for j in range(n + 1):
					si += b[j] * (-1) ** j
				if n % 2 == 1:
					si += M
				if si > s:
					s = si
				a.remove(i + 1)
	else:
		for i in range(a[-1] + 1):
			if i + 1 not in a:
				a.append(i + 1)
				b = sorted(a)
				si = 0
				for j in range(n + 1):
					si += b[j] * (-1) ** j
				if n % 2 == 1:
					si += M
				if si > s:
					s = si
				a.remove(i + 1)
	print(s)


import configparser
import sys
input = sys.stdin.readline

def main():
	(n, m) = [int(x) for x in input().split(' ')]
	a = [int(x) for x in input().split(' ')]
	if a[0] != 0:
		a = [0] + a
	if a[len(a) - 1] != m:
		a = a + [m]
	score = [0 for i in range(len(a))]
	for i in range(len(a) - 1):
		score[i] = a[i + 1] - a[i]
	on = [[0 for i in range(len(a))] for i in range(2)]
	on[1][len(a) - 2] = score[len(a) - 2]
	for i in range(len(a) - 3, -1, -1):
		on[1][i] = score[i] + on[0][i + 1]
		on[0][i] = 0 + on[1][i + 1]
	reg = score[0]
	best = on[1][0]
	if a[1] != 1:
		best = max(best, score[0] - 1 + on[0][1])
	for i in range(1, len(a) - 1):
		if a[i] == a[i + 1]:
			continue
		if i % 2 == 1:
			c = reg + score[i] - 1 + on[0][i + 1]
		else:
			c = reg + score[i] - 1 + on[1][i + 1]
			reg += score[i]
		best = max(best, c)
	print(best)
main()


(N, M) = map(int, input().split())
L = [0] + [int(_) for _ in input().split()] + [M]
sumL = [0]
ans = -10 ** 30
for i in range(1, N + 1):
	sumL.append(sumL[-1] - (-1) ** i * L[i])
for i in range(1, N + 1):
	if L[i] > L[i - 1] + 1:
		ans = max(ans, 2 * sumL[i - 1] - sumL[-1] - (-1) ** i * (L[i] - 1))
	if L[i] < L[i + 1] - 1:
		ans = max(ans, 2 * sumL[i] - sumL[-1] + (-1) ** i * (L[i] + 1))
if N % 2 == 0:
	print(max(ans, sumL[-1] + M))
else:
	print(max(ans + M, sumL[-1]))


(n, m) = [int(z) for z in input().split()]
s = [int(z) for z in input().split()]
allgor = 0
for i in range(n):
	if i == 0:
		allgor += s[i]
	elif i % 2 == 0:
		allgor += s[i] - s[i - 1]
if n % 2 == 0:
	allgor += m - s[n - 1]
j = 0
actgor = 0
maxraz = 0
alldark = m - allgor
for i in range(n):
	if i == 0:
		actgor = s[0]
	elif i % 2 == 0:
		actgor += s[i] - s[i - 1]
	actdark = s[i] - actgor
	if alldark - actdark - allgor + actgor > maxraz:
		maxraz = alldark - actdark - allgor + actgor
if maxraz == 0:
	print(allgor)
else:
	print(allgor + maxraz - 1)


(n, m) = map(int, input().split())
l = sorted(list(map(int, input().split())) + [0, m])
sum_list = [l[i + 1] - l[i] for i in range(len(l) - 1)]
insert = sum(sum_list[1::2]) + sum_list[0] - 1
result = max(sum(sum_list[::2]), insert)
for i in range(2, len(sum_list), 2):
	insert = insert + sum_list[i] - sum_list[i - 1]
	if insert > result:
		result = insert
print(result)


(n, m) = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
l.append(m)
l.insert(0, 0)
n = n + 2
cum_on = [0] * n
for i in range(n - 2, -1, -1):
	cum_on[i] = l[i + 1] - l[i]
	if i != n - 2:
		cum_on[i] = cum_on[i + 2] + cum_on[i]
state = 1
ans = cum_on[0]
temp_ans = 0
for i in range(1, n):
	if l[i] - l[i - 1] < 2:
		if state == 1:
			temp_ans += l[i] - l[i - 1]
		state ^= 1
		continue
	if state == 1:
		ans = max(ans, temp_ans + cum_on[i] + l[i] - l[i - 1] - 1)
		temp_ans += l[i] - l[i - 1]
	else:
		temp = temp_ans + l[i] - l[i - 1] - 1
		if i + 1 < n:
			temp += cum_on[i + 1]
		ans = max(ans, temp)
	state ^= 1
print(ans)


import sys
input = sys.stdin.readline
(n, M) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [M]
(A, B) = (0, 0)
for i in range(n + 1):
	if i % 2 == 0:
		A += a[i + 1] - a[i]
ans = A
for i in range(n + 1):
	if i % 2 == 0:
		A -= a[i + 1] - a[i]
	ans = max(ans, B + (a[i + 1] - a[i] - 1) + (M - a[i + 1] - A))
	if i % 2 == 0:
		B += a[i + 1] - a[i]
print(ans)


(a, b) = [int(x) for x in input().split()]
c = [0] + [int(x) for x in input().split()] + [b]
p = []
T = 0
for i in range(a + 1):
	p.append((c[i + 1] - c[i], [0, 1][i % 2 == 0]))
	T += p[i][0] * p[i][1]
t = [T]
time = T
b = -(-a // 2) * 2
for i in range(0, b, 2):
	time += p[b - 1 - i][0]
	if b - i <= a:
		time -= p[b - i][0]
	if time - 1 > t[-1]:
		t.append(time - 1)
print(t[-1])


(n, M) = map(int, input().split())
morigin = 0
m = 0
maxsum = 0
sumall = 0
s = [0]
s[1:] = [int(x) for x in input().split()]
s.append(M)
for i in range(len(s) - 1):
	maxsum += (1 - 2 * (i % 2)) * (s[i + 1] - s[i])
	morigin += (1 - i % 2) * (s[i + 1] - s[i])
	if i % 2 == 0 and maxsum > m:
		m = maxsum
	if i == len(s) - 2:
		sumall = maxsum
output = int((M + 2 * m - sumall) / 2 - 1)
print(output if output > morigin else morigin)


(n, m) = input().split()
n = int(n)
m = int(m)
a = [int(x) for x in input().split()]
on = []
off = []
presumon = []
presumoff = []
for i in range(0, n + 10):
	presumon.append(0)
	presumoff.append(0)
maxi = -1
tot = 0
for i in range(0, n):
	if i == 0:
		off.append(0)
		on.append(a[i])
	elif i % 2 == 0:
		off.append(0)
		on.append(a[i] - a[i - 1])
	elif i % 2 == 1:
		on.append(0)
		off.append(a[i] - a[i - 1])
if n % 2 == 0:
	a.append(m)
	off.append(0)
	on.append(m - a[n - 1])
else:
	a.append(m)
	on.append(0)
	off.append(m - a[n - 1])
for i in range(0, n + 1):
	tot += on[i]
maxi = tot
for i in range(0, n + 1):
	if i == 0:
		presumon[i] = on[i]
		presumoff[i] = off[i]
	else:
		presumon[i] = presumon[i - 1] + on[i]
		presumoff[i] = presumoff[i - 1] + off[i]
for i in range(0, n + 1):
	tot = 0
	if i == 0:
		if a[i] > 1:
			tot += presumon[i] - 1
			tot += presumoff[n] - presumoff[i - 1]
	elif i % 2 == 0:
		if a[i] - a[i - 1] > 1:
			tot += presumon[i] - 1
			tot += presumoff[n] - presumoff[i - 1]
	elif a[i] - a[i - 1] > 1:
		tot += a[i] - a[i - 1] - 1
		tot += presumon[i - 1]
		tot += presumoff[n] - presumoff[i]
	if maxi < tot:
		maxi = tot
print(maxi)


(n, M) = input().split()
(n, M) = (int(n), int(M))
a = [int(num) for num in input().split(' ')]
a.insert(0, 0)
a.insert(n + 1, M)
currentEmpty = True
if n % 2 == 0:
	currentEmpty = False
(emptySum, sum, index, change) = (0, 0, -1, 0)
for i in range(len(a) - 2, -1, -1):
	if currentEmpty:
		emptySum += a[i + 1] - a[i]
	else:
		sum += a[i + 1] - a[i]
	if emptySum - sum > 1 and currentEmpty and (emptySum - 1 - sum > change):
		index = i
		change = emptySum - 1 - sum
	currentEmpty = not currentEmpty
print(change + sum)


(n, m) = [int(x) for x in input().split()]
s = [int(x) for x in input().split()]
s.insert(0, 0)
s.append(m)
time1 = 0
time2 = 0
for i in range(len(s) - 1):
	if i % 2 == 0:
		time1 += s[i + 1] - s[i]
counter = len(s) - 1
count = 0
temp = 0
while counter > 0:
	count += 1
	if len(s) % 2 == 0:
		if count % 2 == 1:
			temp -= s[counter] - s[counter - 1]
		else:
			temp += s[counter] - s[counter - 1]
	elif count % 2 == 1:
		temp += s[counter] - s[counter - 1]
	else:
		temp -= s[counter] - s[counter - 1]
	time2 = max(temp, time2)
	counter -= 1
if time2 == 0:
	time = time1
else:
	time = time1 + time2 - 1
print(time)


(n, M) = [int(x) for x in input().split()]
arr = [0] + [int(x) for x in input().split()] + [M]
(forward, backward) = ([0], [])
[forward.append(forward[i - 1] + arr[i] - arr[i - 1] if i % 2 == 1 else forward[i - 1]) for i in range(1, n + 2)]
mx = forward[-1]
if n % 2 == 0:
	temp = arr[::-1]
	backward = [0]
	[backward.append(backward[i - 1] + temp[i - 1] - temp[i] if i % 2 == 0 else backward[i - 1]) for i in range(1, n + 2)]
else:
	temp = arr[::-1]
	backward = [0]
	[backward.append(backward[i - 1] + temp[i - 1] - temp[i] if i % 2 == 1 else backward[i - 1]) for i in range(1, n + 2)]
backward = backward[::-1]
i = 0
for (a, b) in zip(arr, arr[1:]):
	res1 = forward[i] + (1 if i % 2 == 0 else b - (a + 1)) + backward[i + 1]
	if a + 1 == b:
		res1 = -1
	res2 = forward[i] + (b - 1 - a if i % 2 == 0 else 1) + backward[i + 1]
	if b - 1 == a:
		res2 = -1
	mx = max(mx, res1, res2)
	i += 1
print(mx)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + a + [m]
temp = 1
b = [0] * len(a)
for i in range(0, len(a), 2):
	b[i] = 1
b[len(a) - 1] = 0
ot = 0
for i in range(len(a)):
	if b[i] == 0 and b[i - 1] == 1:
		ot += a[i] - a[i - 1]
tmp2 = 0
tmp1 = ot
ans = ot
for i in range(len(a) - 1, 0, -1):
	if b[i - 1] == 0:
		if a[i] - a[i - 1] > 1:
			tmp2 += a[i] - a[i - 1] - 1
			ans = max(ans, tmp1 + tmp2)
			tmp2 += 1
		else:
			tmp2 += 1
	elif b[i - 1] == 1:
		tmp1 -= a[i] - a[i - 1]
print(ans)


(n, M) = map(int, input().split())
Nodes = [0]
for x in input().split():
	Nodes.append(int(x))
init = 0
Maxm = 0
for i in range(n):
	Increment = (1 - 2 * (i % 2)) * (Nodes[i + 1] - Nodes[i])
	if Increment < -1:
		Maxm = max(Maxm, init - 1)
	init += Increment
	if Increment > 1:
		Maxm = max(Maxm, init - 1)
init += (1 - 2 * (n % 2)) * (M - Nodes[n])
Maxm = max(Maxm, init)
print(Maxm + (M - init) // 2)


(n, m) = map(int, input().split())
ai = [0]
ai += list(map(int, input().split()))
ai += [m]
num = 1
ans1 = 0
ans2 = 0
ai2 = [0] * (n + 2)
for i in range(1, n + 2):
	ai2[i] = ai2[i - 1]
	if num == 1:
		ai2[i] += ai[i] - ai[i - 1]
	num = 1 - num
maxi = ai2[n + 1]
for i in range(1, n + 1):
	maxi = max(maxi, ai2[i] * 2 + m - ai[i] - ai2[n + 1] - 1)
print(maxi)


(n, M) = map(int, input().split())
arr = list(map(int, input().split()))
arr = [0] + arr + [M]
l1 = [[0, 0] for _ in range(n + 2)]
flag = n % 2 > 0
val = 1
pos = -1
for i in range(n, -1, -1):
	l1[i][flag] += arr[i + 1] - arr[i] + l1[i + 1][flag]
	if flag == 0:
		flag = 1
	else:
		flag = 0
	l1[i][flag] = l1[i + 1][flag]
	if l1[i][1] - l1[i][0] > val:
		val = l1[i][1] - l1[i][0]
		pos = i
print(l1[0][0] + val - 1)


(n, M) = [int(x) for x in input().split()]
line = [0] + [int(x) for x in input().split()] + [M]

def get_line(line):
	l = []
	for i in range(len(line) - 1):
		l.append(line[i + 1] - line[i])
	return l

def get_time(line):
	s = 1
	ans = 0
	for i in line:
		if s == 1:
			ans += i
		s *= -1
	return ans
run = True
l = get_line(line)
t = get_time(l)
for i in range(len(l)):
	a = l[i]
	if a > 1:
		t1 = get_time(l[:i]) + a - 1
		if i % 2 == 0:
			t1 += get_time(l[i + 1:])
		else:
			t1 += get_time(l[i + 2:])
		i0 = i
		j = i
		if t1 > t:
			t = t1
		break
else:
	run = False
if run:
	for i in range(i0 + 1, len(l)):
		if l[i] > 1:
			t1 += get_time(l[2 * ((j + 2) // 2):i + 1])
			t1 -= get_time(l[2 * (j // 2) + 1:i])
			j = i
			if t1 > t:
				t = t1
print(t)


(n, m) = map(int, input().split())
(light, dark, diff) = (0, 0, 1)
for (i, a) in enumerate(reversed([0, *map(int, input().split()), *(m,)[:n & 1]])):
	if i & 1:
		dark += m - a
		if diff < dark - light:
			diff = dark - light
	else:
		light += m - a
	m = a
print(diff + light - 1)


(n, M) = map(int, input().split())
S = [0]
for x in input().split():
	S.append(int(x))
S.append(M)
(S1, S2, SS) = (0, 0, 0)
for i in range(1, n + 2):
	if i % 2 == 1:
		S2 += S[i] - S[i - 1]
	else:
		S1 += S[i] - S[i - 1]
ans = S2
for i in range(1, n + 1, 2):
	SS += S[i] - S[i - 1]
	S2 -= S[i] - S[i - 1]
	if S[i] - 1 > S[i - 1] or S[i] + 1 < S[i + 1]:
		ans = max(ans, SS - 1 + S1)
	S1 -= S[i + 1] - S[i]
print(ans)


(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [m]
off = [0] * (n + 2)
lit = [0] * (n + 2)
for i in range(1, n + 2):
	if i % 2 == 1:
		off[i] = off[i - 1] + a[i] - a[i - 1]
		lit[i] = lit[i - 1]
	else:
		lit[i] = lit[i - 1] + a[i] - a[i - 1]
		off[i] = off[i - 1]
maxi = off[n + 1] + 1
for i in range(1, n + 1):
	diff = off[i] - lit[i + 1]
	diff2 = a[i + 1] - a[i]
	maxi = max(maxi, diff + diff2 + lit[n + 1])
print(maxi - 1)


from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque

def read():
	return int(input())

def readmap():
	return map(int, input().split())

def readlist():
	return list(map(int, input().split()))
(N, M) = readmap()
A = [0] + readlist() + [M]
on_time = []
off_time = []
for i in range(1, N + 2):
	if i % 2 == 1:
		on_time.append(A[i] - A[i - 1])
	else:
		off_time.append(A[i] - A[i - 1])
sum_on_time = sum(on_time)
max_on_time = sum_on_time
if N % 2 == 1:
	i = N + 1
	while i > 0:
		if A[i] - A[i - 1] > 1:
			x = A[i - 1] + 1
			max_on_time = max(max_on_time, sum_on_time + A[i] - x)
		sum_on_time = sum_on_time + (A[i] - A[i - 1]) - (A[i - 1] - A[i - 2])
		if A[i - 1] - A[i - 2] > 1:
			x = A[i - 1] - 1
			max_on_time = max(max_on_time, sum_on_time + x - A[i - 2])
		i -= 2
	print(max_on_time)
else:
	i = N
	sum_on_time -= A[N + 1] - A[N]
	while i > 0:
		if A[i] - A[i - 1] > 1:
			x = A[i - 1] + 1
			max_on_time = max(max_on_time, sum_on_time + A[i] - x)
		sum_on_time = sum_on_time + (A[i] - A[i - 1]) - (A[i - 1] - A[i - 2])
		if A[i - 1] - A[i - 2] > 1:
			x = A[i - 1] - 1
			max_on_time = max(max_on_time, sum_on_time + x - A[i - 2])
		i -= 2
	print(max_on_time)


(n, m) = input().split()
n = int(n)
m = int(m)
a = list(map(int, input().split()))
a.append(m)
b = [int(0) for i in range(n + 1)]
c = [int(0) for i in range(n + 1)]
b[0] = a[0]
ans = int(-1000000007)
for i in range(1, n + 1, 1):
	if i % 2 == 0:
		b[i] = b[i - 1] + a[i] - a[i - 1]
		c[i] = c[i - 1]
	else:
		c[i] = c[i - 1] + a[i] - a[i - 1]
		b[i] = b[i - 1]
for i in range(0, n + 1, 2):
	ans = max(ans, b[i] - 1 + c[n] - c[i])
ans = max(ans, b[n])
print(ans)


(n, k) = [int(i) for i in input().split()]
x = [0] + [int(i) for i in input().split()] + [k]
light = []
s = 0
e = 0
o = 0
even = []
odd = []
for i in range(len(x) - 1):
	s = x[i + 1] - x[i]
	light.append(s)
for i in range(len(light) - 1, -1, -1):
	if i % 2 == 0:
		e += light[i]
	else:
		o += light[i]
	even.append(e)
	odd.append(o)
even = even[::-1]
odd = odd[::-1]
sum = 0
m = 0
for i in range(len(light)):
	if light[i] != 1:
		if i % 2 == 0:
			if i + 1 >= len(light):
				m = max(light[i] - 1 + sum, m)
			else:
				m = max(sum + even[i + 1], m)
		elif i + 1 >= len(light):
			m = max(light[i] - 1 + sum, m)
		else:
			m = max(light[i] - 1 + sum + odd[i + 1], m)
	if i % 2 == 0:
		sum += light[i]
m = max(sum, m)
print(m)


def summ(l, x):
	if x:
		return sum([l[p] for p in range(1, len(l), 2)])
	else:
		return sum([l[p] for p in range(0, len(l), 2)])
m = [int(x) for x in input().split()]
p = [0] + [int(x) for x in input().split()] + [m[1]]
g = tuple([p[i] - p[i - 1] for i in range(1, len(p))])
s = set(g)
h = list(g)
k30 = 2
p = [summ(g, 0)]
for i in range(0, len(g)):
	if g[i] < k30:
		continue
	else:
		if len(s) == 1:
			if not i % 2:
				h[i] -= 1
				h.insert(i + 1, 1)
				p.append(summ(h, 0))
			else:
				h[i] -= 1
				h.insert(i, 1)
				p.append(summ(h, 0))
			break
		k30 = g[i]
		if not i % 2:
			h[i] -= 1
			h.insert(i + 1, 1)
			p.append(summ(h, 0))
		else:
			h[i] -= 1
			h.insert(i, 1)
			p.append(summ(h, 0))
		h = list(g)
print(max(p))


(n, m) = map(int, input().split())
l = [int(x) for x in input().split()]
a = 0
if n % 2 != 0:
	l.append(m)
	lst = [0] + l
	a = sum(((-1) ** n * lst[n] for n in range(len(lst)))) - m
else:
	lst = [0] + l
	a = sum(((-1) ** n * lst[n] for n in range(len(lst)))) - m
add1 = 0
add2 = sum(((-1) ** n * lst[n] for n in range(len(lst))))
for i in range(len(lst) - 1):
	if lst[i + 1] - lst[i] != 1:
		if i % 2 == 0:
			a = min(a, add1 + -1 * (lst[i + 1] - 1) - add2)
		else:
			a = min(a, add1 + (lst[i] + 1) - add2)
	add1 -= lst[i + 1] * (-1) ** i
	add2 += lst[i + 1] * (-1) ** i
print(-1 * a)


(n, M) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
a.insert(0, 0)
n += 1
lit = [0] * (n + 1)
for i in range(1, n):
	if i % 2 == 0:
		lit[i] = lit[i - 1]
	else:
		lit[i] = lit[i - 1] + a[i] - a[i - 1]
if n % 2 == 0:
	lit[n] = lit[n - 1]
else:
	lit[n] = lit[n - 1] + M - a[n - 1]
ans = lit[n]
for i in range(n):
	pre_lit = lit[i]
	post_lit = M - a[i] - (lit[n] - lit[i])
	if i > 0 and a[i - 1] + 1 < a[i]:
		if i % 2 == 0:
			ans = max(ans, pre_lit + 1 + post_lit)
		else:
			ans = max(ans, pre_lit - 1 + post_lit)
	if i + 1 < n and a[i] + 1 < a[i + 1] or (i + 1 == n and a[n - 1] + 1 < M):
		if i % 2 == 0:
			ans = max(ans, pre_lit + post_lit + 1)
		else:
			ans = max(ans, pre_lit + post_lit - 1)
print(ans)


(n, m) = map(int, input().split())
x = [0] + [int(i) for i in input().split()] + [m]
on_time = sum(x[1::2]) - sum(x[::2])
if len(x) % 2 != 0:
	on_time += x[-1]
off_time = max_time = current_time = 0
for i in range(1, len(x), 2):
	off_time += x[i] - x[i - 1]
	current_time = on_time - off_time
	max_time = max(max_time, off_time + m - x[i] - current_time - 1)
print(max(on_time, max_time))


(n, M) = map(int, input().split())
a = [0] + [int(x) for x in input().split()] + [M]
l = []
rl = []
maxl = 0
for i in range(len(a) - 1):
	l.append(a[i + 1] - a[i])
	rl.append(a[i + 1] - a[i])
for i in range(1, len(l) - 1):
	rl[-i - 2] += rl[-i]
for i in range(2, len(l)):
	l[i] += l[i - 2]
for i in range(len(l)):
	if l[i] != 1:
		if i & 1:
			maxl = max(maxl, l[i - 1] + rl[i] - 1)
		else:
			t = rl[i + 1] if i + 1 < len(rl) else 0
			maxl = max(maxl, l[i] - 1 + t)
t = len(l) - 1 & 1
maxl = max(maxl, l[-1 - t])
print(maxl)


import sys, math, queue
MOD = 998244353
sys.setrecursionlimit(1000000)
(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [m]
(x, y) = ([], [])
for i in range(1, n + 2):
	if i % 2 == 1:
		if len(x) == 0:
			x.append(a[i] - a[i - 1])
		else:
			x.append(x[-1] + a[i] - a[i - 1])
	elif len(y) == 0:
		y.append(a[i] - a[i - 1])
	else:
		y.append(y[-1] + a[i] - a[i - 1])
x.append(0)
y.append(0)
ans = x[-2]
for i in range(1, n + 2):
	if a[i] - a[i - 1] < 2:
		continue
	ii = (i - 1) // 2
	if i % 2 == 1:
		ans = max(ans, x[ii] - 1 + y[-2] - y[ii - 1])
	else:
		ans = max(ans, x[ii] + a[i] - a[i - 1] - 1 + y[-2] - y[ii])
print(ans)


(n, M) = map(int, input().split(' '))
a = input().split(' ')
for i in range(n):
	a[i] = int(a[i])
a.insert(0, 0)
a.append(M)
p = 0
o = 0
for i in range(1, n + 2):
	if i % 2 == 1:
		p += a[i] - a[i - 1]
	else:
		o += a[i] - a[i - 1]
raz = p
ind = -1
a_p = 0
a_o = 0
for i in range(1, n + 2):
	if i % 2 == 0:
		if a[i] - a[i - 1] != 1:
			if a_p - 1 + o > raz:
				raz = a_p - 1 + o
		o -= a[i] - a[i - 1]
		a_o += a[i] - a[i - 1]
	else:
		if a[i] - a[i - 1] != 1:
			if a_p + a[i] - a[i - 1] - 1 + o > raz:
				raz = a_p + a[i] - a[i - 1] - 1 + o
		p -= a[i] - a[i - 1]
		a_p += a[i] - a[i - 1]
print(raz)


(n, m) = map(int, input().split())
program = [0] + [int(x) for x in input().split()] + [m]
ori_off = 0
ori_on = 0
final = 0
for i in range(1, n + 2):
	if i % 2 == 0:
		ori_off += program[i] - program[i - 1]
	else:
		ori_on += program[i] - program[i - 1]
maximum = ori_on
for i in range(1, n + 1, 2):
	final += program[i] - program[i - 1]
	if program[i] - program[i - 1] > 1 or program[i + 1] - program[i] > 1:
		maximum = max(maximum, final - 1 + ori_off)
	ori_off -= program[i + 1] - program[i]
print(maximum)


(n, m) = map(int, input().split(' '))
ope = [0] * n
s = input().split(' ')
for i in range(n):
	ope[i] = int(s[i])
ope.append(m)
on = [ope[0]]
off = []
i = 0
light = False
while i < n:
	if light:
		on.append(ope[i + 1] - ope[i])
	else:
		off.append(ope[i + 1] - ope[i])
	i += 1
	light = not light
(a, b) = (len(on) - 1, len(off) - 1)
onsum = 0
offsum = 0
delta = 0
if a > b:
	onsum = on[a]
while b >= 0:
	offsum += off[b]
	if offsum - onsum - 1 > delta:
		delta = offsum - onsum - 1
	onsum += on[b]
	b -= 1
sm = onsum + delta
print(sm)


(n, M) = map(int, input().split())
initprog = [0]
initprog += list(map(int, input().split()))
initprog += [M]
interval = [y - x for (x, y) in zip(initprog, initprog[1:])]
b = sum(interval[::2])
a = 0
c = 0
if n % 2 == 0:
	for i in range(n, 1, -2):
		a += interval[i - 1] - interval[i]
		c = max(c, a)
	if c > 1:
		b += c - 1
else:
	c += interval[n]
	a += interval[n]
	for i in range(n - 1, 1, -2):
		a += interval[i - 1] - interval[i]
		c = max(c, a)
	if c > 1:
		b += c - 1
print(b)


(n, M) = map(int, input().split(' '))
a = [0] + list(map(int, input().split(' ')))
a.append(M)
before = [0] * (n + 10)
op = 1
for i in range(1, n + 2):
	before[i] = before[i - 1] + op * (a[i] - a[i - 1])
	op = 1 - op
outcome = before[n + 1]
for i in range(1, n + 1):
	if a[i + 1] == a[i] + 1:
		continue
	outcome = max(outcome, before[i] + M - a[i] - int(before[i + 1] == before[i]) - (before[n + 1] - before[i]))
print(outcome)


(n, m) = [int(i) for i in input().split()]
a = [*map(int, input().split())] + [m]
min_time = m
time = 0
for i in reversed(range(1, n + 1)):
	if i % 2 == 0:
		wk1 = 1
	else:
		wk1 = -1
	time += wk1 * (a[i] - a[i - 1])
	if time < min_time:
		min_time = time
		position = a[i - 1] + -wk1
if min_time >= 0:
	position = m
count = 1
i = 1
ans = 0
a = [0] + a
while i < n + 2:
	if a[i] > position > a[i - 1]:
		ans += count % 2 * (position - a[i - 1])
		count += 1
		ans += count % 2 * (a[i] - position)
	else:
		ans += count % 2 * (a[i] - a[i - 1])
	count += 1
	i += 1
print(ans)


import copy
(n, M) = map(int, input().split())
s = list(map(int, input().split()))
lengths = []
i1 = []
z1 = []
s.append(0)
s.append(M)
s.sort()
l = len(s)
length = 0
for n in range(1, l, 2):
	length += s[n] - s[n - 1]
	i1.append(s[n] - s[n - 1])
lengths.append(length)
x1 = [2 * i1.index(max(i1))]
if max(i1) > 1 and i1.count(max(i1)) != len(i1):
	for ii in range(i1.count(max(i1)) - 1):
		x = i1.index(max(i1), int(0.5 * x1[-1] + 1))
		x1.append(2 * x)
x2 = set(x1)
z1.append(s[-2] + 1)
for x in x2:
	for y in [-1, 1]:
		z = s[x + y] + 1
		z1.append(z)
z2 = set(z1) - set(s) - {M + 1}
for zz in z2:
	ss = copy.deepcopy(s)
	ss.append(zz)
	ss.sort()
	l = len(ss)
	length = 0
	for n in range(1, l, 2):
		length += ss[n] - ss[n - 1]
	lengths.append(length)
print(max(lengths))


(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [m]
b = [0] * (n + 2)
for i in range(1, n + 2, 2):
	b[i] = a[i] - a[i - 1]
for i in range(1, n + 2):
	b[i] += b[i - 1]
ans = b[-1]
for i in range(n + 2):
	if i > 0 and a[i] > a[i - 1] + 1:
		x = b[i] + m - a[i] - (b[-1] - b[i])
		if i % 2:
			x -= 1
		else:
			x += 1
		ans = max(ans, x)
	if i + 1 < n + 2 and a[i] < a[i + 1] - 1:
		x = b[i] + m - a[i] - (b[-1] - b[i])
		if i % 2:
			x -= 1
		else:
			x += 1
		ans = max(ans, x)
print(ans)


MIS = lambda : map(int, input().split())
(n, m) = MIS()
a = [0] + list(MIS()) + [m]
inter = []
for i in range(n + 1):
	inter.append(a[i + 1] - a[i])
S = sum(inter[::2])
opt = S
cur = S
mul = 1 if n % 2 == 1 else -1
x = m
for i in range(n, 0, -1):
	if a[i] + 1 != a[i + 1]:
		cur += (x - a[i] - 1) * mul
		opt = max(opt, cur)
		x = a[i] + 1
	cur += (x - a[i]) * mul
	x = a[i]
	mul *= -1
	if a[i] - 1 != a[i - 1]:
		cur += mul
		opt = max(opt, cur)
		x -= 1
print(opt)


R = lambda : map(int, input().split())
(n, M) = R()
a = list(R())
a = [0] + a + [M]
b = [0] * (n + 2)
c = [0] * (n + 2)
for i in range(1, n + 2):
	if i % 2:
		b[i] = b[i - 1] + a[i] - a[i - 1]
		c[i] = c[i - 1]
	else:
		b[i] = b[i - 1]
		c[i] = c[i - 1] + a[i] - a[i - 1]
ans = b[n + 1]
for i in range(0, n + 1):
	if i % 2:
		k = a[i] + 1
		if k == a[i + 1]:
			continue
		t = b[i] + (c[n + 1] - c[i + 1]) + a[i + 1] - k
	else:
		k = a[i + 1] - 1
		if k == a[i]:
			continue
		t = b[i + 1] + (c[n + 1] - c[i]) - 1
	ans = max(ans, t)
print(ans)


(_, M) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
if a[0] != 0:
	a.insert(0, 0)
if a[-1] != M:
	a.append(M)
light = []
dark = []
for i in range(len(a) // 2):
	light.append(a[2 * i + 1] - a[2 * i])
	if 2 * i + 2 < len(a):
		dark.append(a[2 * i + 2] - a[2 * i + 1])
total_light = sum(light)
total_dark = sum(dark)
pre_sum = 0
post_sum = total_light
for i in range(len(light)):
	v = light[i]
	light[i] = (pre_sum, v, post_sum - light[i])
	pre_sum += v
	post_sum -= v
pre_sum = 0
post_sum = total_dark
for i in range(len(dark)):
	v = dark[i]
	dark[i] = (pre_sum, v, post_sum - dark[i])
	pre_sum += v
	post_sum -= v
max = max(total_light, total_dark)
for i in range(len(light)):
	(pre, v, post) = light[i]
	if i < len(dark):
		sum = pre + v - 1 + dark[i][2]
		if sum > max:
			max = sum
for i in range(len(dark)):
	(pre, v, _) = light[i]
	pre = pre + v
	(_, v, post) = dark[i]
	sum = pre + v - 1 + post
	if sum > max:
		max = sum
print(max)