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: interview

Starter code:

Solutions:
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 = 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 =list(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)


3

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))


def __starting_point():
    main()

__starting_point()

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)
    else:
        if 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)
            
        


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
        else:
            if i-prev != 1:
                tmp = prevOn+i-prev-1+m-i-(on-prevOn)
                if tmp > ans:
                    ans = tmp
        prev = i
        counter+=1
    print(ans)


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)]
# print(times)
light = times[::2]
dark = times[1::2]

light_time = list(accumulate(light))
dark_time  = [0]+ list(accumulate(dark))
# print(light_time, dark_time)
res = light_time[-1]
for i in range(tt):
    if times[2*i] >1: # если горит больше минуты
        # print('light to ', i, ' is ', light_time[i]-1, dark_time[-1]-dark_time[i], 'if switching light off')

        res = max(res, light_time[i]-1 + (dark_time[-1]-dark_time[i]))

    if i == 0 or times[2*i-1] >1: # если не горит больше минуты
        # print('light to ', i, ' is ', light_time[i], dark_time[-1]-dark_time[i] -1)

        res = max(res, light_time[i] + dark_time[-1]-dark_time[i] -1)
print(res)

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]

        
    else:
        if 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 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()))


# B
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 = 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, 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)
        else:

            if 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)


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]

# print(a)

for i in range(1, n):
	prev[i] = prev[i-1] + prev[i]

# print(prev)


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(flip)

print(max(prev[-1], max(prev[i] + flip[i+1] + abs(a[i+1] - a[i] - 1) for i in range(n-1))))

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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()
#print(finish - start)


n, m = list(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_d = sum_l + 1
        fake_l = sum_d - 1
    else:
        # fake_d = sum_l - dis + 1
        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)
# 奇数 暗(1)，偶数 亮


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)

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:]):
  # print("%d or %d: " % (a+1, b-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
  # print("%d - %d: " % (res1, res2))
  mx = max(mx, res1, res2)
  i += 1

print(mx)

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=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)

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
    # dbvar(t)
    ans = max(ans, t)
print(ans)

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]
# print(fwd)
# print(bwd)
# print(fwd_)
# print(bwd_)
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)



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()

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)



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)

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 # added in pos between i and i+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)
    
def __starting_point():
    main()
__starting_point()