Problem:
 Score : 800 points    Problem Statement Takahashi Lake has a perimeter of L . On the circumference of the lake, there is a residence of the lake's owner, Takahashi.
Each point on the circumference of the lake has a coordinate between 0 and L (including 0 but not L ), which is the distance from the Takahashi's residence, measured counter-clockwise.  There are N trees around the lake; the coordinate of the i -th tree is X_i . There is no tree at coordinate 0 , the location of Takahashi's residence.  Starting at his residence, Takahashi will repeat the following action:   If all trees are burnt, terminate the process.  Specify a direction: clockwise or counter-clockwise.  Walk around the lake in the specified direction, until the coordinate of a tree that is not yet burnt is reached for the first time.  When the coordinate with the tree is reached, burn that tree, stay at the position and go back to the first step.   Find the longest possible total distance Takahashi walks during the process.      Partial Score A partial score can be obtained in this problem:   300 points will be awarded for passing the input satisfying N \leq 2000 .       Constraints  2 \leq L \leq 10^9  1 \leq N \leq 2\times 10^5  1 \leq X_1 < ... < X_N \leq L-1  All values in input are integers.         Input Input is given from Standard Input in the following format:  L  N  X_1  :  X_N       Output Print the longest possible total distance Takahashi walks during the process.        Sample Input 1 10 3
2
7
9      Sample Output 1 15  Takahashi walks the distance of 15 if the process goes as follows:   Walk a distance of 2 counter-clockwise, burn the tree at the coordinate 2 and stay there.  Walk a distance of 5 counter-clockwise, burn the tree at the coordinate 7 and stay there.  Walk a distance of 8 clockwise, burn the tree at the coordinate 9 and stay there.        Sample Input 2 10 6
1
2
3
6
7
9      Sample Output 2 27       Sample Input 3 314159265 7
21662711
77271666
89022761
156626166
160332356
166902656
298992265      Sample Output 3 1204124749

Solution (Python):

from itertools import accumulate
L, N = map(int, input().split())
X = [0] + [int(input()) for _ in range(N)]
Y = [0] + [L - x for x in X[1:]][::-1]

sx = list(accumulate(X))
sy = list(accumulate(Y))

ans = 0
for i in range(1, N + 1):
    j = N - i

    mn = min(i - 1, j)
    now = X[i]
    now += 2 * (sx[i - 1] - sx[i - 1 - mn]) + 2 * (sy[j] - sy[j - mn - (j > mn)])
    ans = max(ans, now)

for i in range(N):
    j = N - i

    mn = min(i, j - 1)
    now = Y[j]
    now += 2 * (sx[i] - sx[i - mn - (i > mn)]) + 2 * (sy[j - 1] - sy[j - 1 - mn])
    ans = max(ans, now)

print(ans)

Solution (Python):

from itertools import accumulate
L, N = map(int, input().split())
X = [int(input()) for _ in range(N)]
Y = [L - x for x in X][::-1]

sx = [0] + list(accumulate(X))
sy = [0] + list(accumulate(Y))

ans = 0
for i in range(N):
    j = N - i - 1
    mn = min(i, j)

    now = X[i]
    now += 2 * (sx[i] - sx[i - mn]) + 2 * (sy[j] - sy[j - mn - (i < j)])
    ans = max(ans, now)

    now = Y[j]
    now += 2 * (sx[i] - sx[i - mn - (i > j)]) + 2 * (sy[j] - sy[j - mn])
    ans = max(ans, now)

print(ans)

Solution (Python):
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(5000000)



def partial():
    L, N = [int(elem) for elem in fin().split()]
    X_list = [0]
    X_list.extend([int(fin()) for _ in range(N)])
    X_list.append(L)
    N += 2

    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    


    
    
    dp = [[[0] * 2 for _ in range(N + 1)] for _ in range(N + 1)]

    for w in range(1, N + 1):
        for start in range(1, N - w):
            end = start + w
            dp[start][end][1] = max(dp[start + 1][end][1] + X_list[start] - X_list[start - 1],
                                    dp[start][end - 1][0] + L + X_list[start - 1] - X_list[end - 1])
            dp[start][end][0] = max(dp[start + 1][end][1] + L + X_list[start] - X_list[end],
                                    dp[start][end - 1][0] + X_list[end] - X_list[end - 1])

    return max(dp[1][N - 1])


def perfect():
    L, N = [int(elem) for elem in fin().split()]
    X_list = [int(fin()) for _ in range(N)]

    
    prefix_sum_X = [0] * N
    suffix_reverse_sum_X = [0] * N
    cur_sum = 0
    for i, X in enumerate(X_list):
        cur_sum += X
        prefix_sum_X[i] = cur_sum
    cur_sum = 0
    for i in reversed(range(N)):
        cur_sum += L - X_list[i]
        suffix_reverse_sum_X[i] = cur_sum
    
    max_dist = max(X_list[-1], L - X_list[0])
    
    for i in range(N - 1):
        
        stopping_idx = i + (N - i) // 2
        if (N - i - 1) % 2 == 0:
            dist = 2 * X_list[i] + (prefix_sum_X[stopping_idx] - prefix_sum_X[i]) * 2 \
                                 + (suffix_reverse_sum_X[stopping_idx + 1]) * 2 \
                                 - X_list[stopping_idx]
        else:
            dist = 2 * X_list[i] + (prefix_sum_X[stopping_idx - 1] - prefix_sum_X[i]) * 2 \
                                 + (suffix_reverse_sum_X[stopping_idx]) * 2 \
                                 - (L - X_list[stopping_idx])
        
        max_dist = max(max_dist, dist)
    
    
    for i in range(1, N):
        stopping_idx = (N - i) // 2
        if (N - i) % 2 == 1:
            dist = 2 * (L - X_list[N - i]) + (suffix_reverse_sum_X[stopping_idx + 1] - suffix_reverse_sum_X[N - i]) * 2 \
                                           + prefix_sum_X[stopping_idx] * 2 \
                                           - X_list[stopping_idx]
        else:
            dist = 2 * (L - X_list[N - i]) + (suffix_reverse_sum_X[stopping_idx] - suffix_reverse_sum_X[N - i]) * 2 \
                                           + prefix_sum_X[stopping_idx - 1] * 2 \
                                           - (L - X_list[stopping_idx])
        
        max_dist = max(max_dist, dist)
    return max_dist


print(perfect())

Solution (Python):
(L, N) = map(int, input().split())
X = [0 for i in range(N)]
sumld = [0 for i in range(N)]
sumrd = [0 for i in range(N)]
for i in range(N):
    X[i] = int(input())
    sumld[i] = X[i]*2 if i == 0 else sumld[i-1] + X[i]*2
for i in range(N):
    sumrd[N-1-i] = (L-X[N-1-i])*2 if i == 0 else sumrd[N-1-i+1] + (L-X[N-1-i])*2




ans = 0
if N == 1:
    ans = max(X[0], L-X[0])
else:
    dmax = 0
    for i in range(1, N):
        l = (N-1+i)%N
        r = i
        lnum = l+1
        rnum = N-lnum
        
        
        
        

        
        d = 0
        
        if lnum > rnum:
            d = sumld[l] + sumrd[r] - X[l]
            if lnum-rnum > 1:
                d -= sumld[l-rnum-1]
        
        else:
            d = sumld[l] + sumrd[r] - X[l]
            if rnum-lnum > 0:
                d -= sumrd[r+lnum]
        
        if d > dmax:
            dmax = d

        
        d = 0
        
        if lnum >= rnum:
            d = sumld[l] + sumrd[r] - (L-X[r])
            if lnum-rnum > 0:
                d -= sumld[l-rnum]
        
        else:
            d = sumld[l] + sumrd[r] - (L-X[r])
            if rnum-lnum > 1:
                d -= sumrd[r+lnum+1]
        
        if d > dmax:
            dmax = d
    ans = dmax

print(ans)

Solution (Python):
L, N = map(int, input().split())
X = [int(input()) for i in range(N)]
Y = [L - X[-i] for i in range(1, N + 1)]


def check(T, N):
    X = [0] + T
    P = [0] * (N + 1)
    Q = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = P[i - 1] + X[i]
    for i in range(N, 0, -1):
        Q[i - 1] = Q[i] + L - X[i]
    ans = -1
    for i in range(1, N + 1):
        k = N - i
        if k % 2 == 0:
            a = k // 2
            t = 2 * (P[i + a - 1] - P[i - 1]) + 2 * (Q[i + a]) + X[i + a]
        else:
            a = k // 2
            t = 2 * (P[i + a] - P[i - 1]) + 2 * (Q[i + a + 1]) + L - X[i + a + 1]
        ans = max(ans, t)
        
    return ans


print(max(check(X, N), check(Y, N)))

Solution (Python):
from itertools import accumulate

def getRangeSum(accXs, iFr, iTo):
    return accXs[iTo+1] - accXs[iFr]

def getAns(accXs, accRevXs, Xs, revXs):
    ans = 0
    for i in range(N):
        num = (N-i)//2
        dist = 2 * getRangeSum(accXs, i, i + num-1)
        dist += 2 * getRangeSum(accRevXs, 0, num-1)
        if (N-i)%2 == 0:
            dist -= revXs[num-1]
        else:
            dist += Xs[i + num]
        ans = max(ans, dist)
    return ans

L, N = map(int, input().split())
Xs = [int(input()) for _ in range(N)]

revXs = [L-X for X in reversed(Xs)]
accXs = [0] + list(accumulate(Xs))
accRevXs = [0] + list(accumulate(revXs))

print(max(getAns(accXs, accRevXs, Xs, revXs), getAns(accRevXs, accXs, revXs, Xs)))

Solution (Python):


import sys


input = sys.stdin.readline


def inpl(): return list(map(int, input().split()))


L, N = inpl()
X = [int(input()) for _ in range(N)]

if N == 1:
    print(max(X[0], L - X[0]))
    exit()


Xcc = [0]  
Xc = [0]  
for i in range(N):  
    Xcc.append(Xcc[-1] + X[i] * 2)
    Xc.append(Xc[-1] + (L - X[-(1 + i)]) * 2)




ans = 0
if N % 2:
    for i in range(1, N):
        
        t_ccw = (N + i) // 2  
        t_cw = N - t_ccw  
        ans_ccw = Xcc[t_ccw] - Xcc[i - 1] + Xc[t_cw]
        ans_ccw -= X[t_ccw - 1] if i % 2 else (L - X[-t_cw])  

        
        t_cw = (N + i) // 2
        t_ccw = N - t_cw
        ans_cw = Xc[t_cw] - Xc[i - 1] + Xcc[t_ccw]
        ans_cw -= (L - X[-t_cw]) if i % 2 else X[t_ccw - 1]

        ans = max(ans, ans_ccw, ans_cw)


else:
    for i in range(1, N):
        
        t_ccw = (N + i) // 2
        t_cw = N - t_ccw
        ans_ccw = Xcc[t_ccw] - Xcc[i - 1] + Xc[t_cw]
        ans_ccw -= (L - X[-t_cw]) if i % 2 else X[t_ccw - 1]

        
        t_cw = (N + i) // 2
        t_ccw = N - t_cw
        ans_cw = Xc[t_cw] - Xc[i - 1] + Xcc[t_ccw]
        ans_cw -= X[t_ccw - 1] if i % 2 else (L - X[-t_cw])

        ans = max(ans, ans_ccw, ans_cw)

print(ans)

Solution (Python):


import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


L, N = inpl()
X = [int(input()) for _ in range(N)]

if N == 1:
    print(max(X[0], L - X[0]))
    exit()


Xcc = [0]  
Xc = [0]  
for i in range(N):
    Xcc.append(Xcc[-1] + X[i] * 2)
    Xc.append(Xc[-1] + (L - X[-(1 + i)]) * 2)




ans = 0
if N % 2:
    for i in range(1, N):
        
        t_ccw = (N + i) // 2
        t_cw = N - t_ccw
        ans_ccw = Xcc[t_ccw] - Xcc[i - 1] + Xc[t_cw]
        ans_ccw -= X[t_ccw - 1] if i % 2 else (L - X[-t_cw])

        
        t_cw = (N + i) // 2
        t_ccw = N - t_cw
        ans_cw = Xc[t_cw] - Xc[i - 1] + Xcc[t_ccw]
        ans_cw -= (L - X[-t_cw]) if i % 2 else X[t_ccw - 1]

        ans = max(ans, ans_ccw, ans_cw)


else:
    for i in range(1, N):
        
        t_ccw = (N + i) // 2
        t_cw = N - t_ccw
        ans_ccw = Xcc[t_ccw] - Xcc[i - 1] + Xc[t_cw]
        ans_ccw -= (L - X[-t_cw]) if i % 2 else X[t_ccw - 1]

        
        t_cw = (N + i) // 2
        t_ccw = N - t_cw
        ans_cw = Xc[t_cw] - Xc[i - 1] + Xcc[t_ccw]
        ans_cw -= X[t_ccw - 1] if i % 2 else (L - X[-t_cw])

        ans = max(ans, ans_ccw, ans_cw)

print(ans)

Solution (Python):
import sys

def 解():
    L,N=[int(_) for _ in input().split()]
    aX=[int(_) for _ in sys.stdin.readlines()]
    iMax = max(aX[0],L-aX[0],aX[-1],L-aX[-1])
    
    accX={}
    accX[-1]=0
    accX[0]=aX[0]
    for i in range(1,N):
        accX[i]=accX[i-1]+aX[i]
    dMemo = {}
    def getAccX(iS,iE):
        if (iS,iE) in dMemo:
            return dMemo[(iS,iE)]
        else:
            r = accX[iE]-accX[iS]
            dMemo[(iS,iE)] = r
            return r
    if 1 < N:
        for i in range(N-1):
            lN = min(i,N-i-1)
            rN = min(i+1,N-i-1)
            
            
            R1 = aX[i]+ 2*(getAccX(i-lN-1,i-1)) + 2*(rN*L-(getAccX(i,i+rN)))
            i += 1
            lN = min(i,N-i)
            rN = min(i,N-i-1)
            
            
            R2 = (L- aX[i])+ 2*(getAccX(i-lN-1,i-1)) + 2*(rN*L-getAccX(i,i+rN))

            iMax = max(R1,R2,iMax)
    print(iMax)
解()

Solution (Python):
import sys
def 解():
    L,N=[int(_) for _ in input().split()]
    aX=[int(_) for _ in sys.stdin.readlines()]
    iMax = max(aX[0],L-aX[0],aX[-1],L-aX[-1])
    accX = [0]*(N+1)
    accX[0]=aX[0]
    for i in range(1,N):
        accX[i]=accX[i-1]+aX[i]

    if 1 < N:
        for i in range(N-1):

            lN = min(i,N-i-1)
            rN = min(i+1,N-i-1)
            
            R1 = aX[i]+ 2*(accX[i-1]-accX[i-lN-1]) + 2*(rN*L-(accX[i+rN]-accX[i]))

            i += 1
            lN = min(i,N-i)
            rN = min(i,N-i-1)
            
            R2 = (L- aX[i])+ 2*(accX[i-1]-accX[i-lN-1]) + 2*(rN*L-(accX[i+rN]-accX[i]))

            iMax = max(R1,R2,iMax)
    print(iMax)
解()

Solution (Python):
import sys
def main():
    L, N = map(int, input().split())
    lines = sys.stdin.readlines()

    trees_ccw = [None] * N
    for i in range(N):
        trees_ccw[i] = int(lines[i])

    trees_cw = [L - trees_ccw[-(i+1)] for i in range(N)]
    trees_ccw_accum = [0] + [None] * N
    trees_cw_accum = [0] + [None] * N
    for i in range(N):
        trees_ccw_accum[i+1] = trees_ccw_accum[i] + trees_ccw[i]
        trees_cw_accum[i+1] = trees_cw_accum[i] + trees_cw[i]

    
    
    
    

    dist_max = 0

    for i in range(1,N+1):
        offset_left = i
        n_left = offset_left + (N-offset_left) // 2 
        n_right = N - n_left    



        '''
        [print('L', end='') for _ in range(offset_left-1)]
        print('L', end='_')
        for i_ in range(N-offset_left):
            if i_ % 2 == 0:
                print('R', end='')
            else:
                print('L', end='')
        print()
        print(offset_left, n_left, n_right)
        '''


        dist_1 = 2 * (trees_ccw_accum[n_left] - trees_ccw_accum[i-1]) + 2 * trees_cw_accum[n_right]
        dist_2 = 2 * (trees_cw_accum[n_left] - trees_cw_accum[i-1]) + 2 * trees_ccw_accum[n_right]



        if (N-offset_left) % 2 == 0:
            dist_1 -= trees_ccw[n_left-1]
            dist_2 -= trees_cw[n_left-1]
        else:
            dist_1 -= trees_cw[n_right-1]
            dist_2 -= trees_ccw[n_right-1]

        if dist_max < dist_1:
            dist_max = dist_1

        if dist_max < dist_2:
            dist_max = dist_2

        

    print(dist_max)
    return

main()

Solution (Python):
L , n = map(int, input().split())
a = [int(input()) for i in range(n)]


psumL = [0 for i in range(n + 2)]
for i in range(n) :
    psumL[i + 1] = psumL[i] + a[i];
psumR = [0 for i in range(n + 2)]
for i in range(n) :
    psumR[n - i] = psumR[n - i + 1] + L - a[n - i - 1];


ans = max(a[n - 1], L - a[0])
for useL in range(1, n) :
    useR = n - useL
    if (useL == useR) : 
        ans = max(ans, 2 * (psumL[useL] + psumR[n - useR + 1]) - min(a[useL  - 1], L - a[n - useR]))
    if (useL > useR) : 
        skipL = useL - useR 
        ans = max(ans, 2 * (psumL[useL] - psumL[skipL] + psumR[n - useR + 1]) - (L - a[n - useR]))
        ans = max(ans, 2 * (psumL[useL] - psumL[skipL - 1] + psumR[n - useR + 1]) - a[useL - 1])
    if (useR > useL) :
        skipR = useR - useL
        
        ans = max(ans, 2 * (psumL[useL] + psumR[n - useR + 1] - psumR[n - skipR + 1]) - a[useL - 1])
        ans = max(ans, 2 * (psumL[useL] + psumR[n - useR + 1] - psumR[n - skipR + 2]) - (L - a[n - useR]))

print(ans)

Solution (Python):
import sys

l, n = map(int, input().split())
x = [int(input()) for _ in range(n)]

x_sum = [0]
for i in range(n):
	x_sum.append(x_sum[-1] + x[i])
ans = x[-1]
for i in range(n-1):
	num = x[i]
	e = (i+n) // 2
	if (n-1-i) % 2 == 1:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i]
		num -= 2 * (x_sum[n] - x_sum[e]) - x[e]
	else:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i] + x[e]
		num -= 2 * (x_sum[n] - x_sum[e+1])

	ans = max(ans, num)

x = [l-x[n-i] for i in range(1, n+1)]

x_sum = [0]
for i in range(n):
	x_sum.append(x_sum[-1] + x[i])
for i in range(n-1):
	num = x[i]
	e = (i+n) // 2
	if (n-1-i) % 2 == 1:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i]
		num -= 2 * (x_sum[n] - x_sum[e]) - x[e]
	else:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i] + x[e]
		num -= 2 * (x_sum[n] - x_sum[e+1])

	ans = max(ans, num)

print(ans)

Solution (Python):
import sys

l, n = map(int, input().split())
x = [int(input()) for _ in range(n)]

x_sum = [0]
for i in range(n):
	x_sum.append(x_sum[-1] + x[i])
ans = x[-1]
for i in range(n-1):
	num = x[i]
	e = (i+n) // 2
	if (n-1-i) % 2 == 1:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i]
		num -= 2 * (x_sum[n] - x_sum[e]) - x[e]
	else:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i] + x[e]
		num -= 2 * (x_sum[n] - x_sum[e+1])

	ans = max(ans, num)

x = [l-x[n-i] for i in range(1, n+1)]

x_sum = [0]
for i in range(n):
	x_sum.append(x_sum[-1] + x[i])
for i in range(n-1):
	num = x[i]
	e = (i+n) // 2
	if (n-1-i) % 2 == 1:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i]
		num -= 2 * (x_sum[n] - x_sum[e]) - x[e]
	else:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i] + x[e]
		num -= 2 * (x_sum[n] - x_sum[e+1])

	ans = max(ans, num)

print(ans)

Solution (Python):

L,N = list(map(int,input().split()))
X=[]
Y=[]
SX=[0]
SY=[0]
sx=0
sy=0
for i in range(N):
   x=int(input())
   X.append(x)
   sx+=x
   SX.append(sx)
   Y.append(L-x)
   sy+=L-x
   SY.append(sy)   

max_score=0   
for i in range(N):
    if i>N-i-1:
        max_score=max(2*(SX[i]-SX[2*i-N])+2*(SY[N]-SY[i+1])+Y[i],max_score)
    elif i<N-i-1:
        max_score=max(2*(SX[i]-SX[0])+2*(SY[2*i+2]-SY[i+1])+X[i],max_score)

        
    ind = min(i,N-i-1)
    max_score=max(2*(SX[i]-SX[i-ind])+2*(SY[i+ind+1]-SY[i+1])+X[i],max_score)
    max_score=max(2*(SX[i]-SX[i-ind])+2*(SY[i+ind+1]-SY[i+1])+Y[i],max_score)


print(max_score)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    l,n = LI()
    x = [I() for _ in range(n)]
    if n == 1:
        return max(x[0], l-x[0])

    ir = [0]
    for c in x:
        ir.append(ir[-1] + c*2)
    jr = [0]
    for c in x[::-1]:
        jr.append(jr[-1] + (l-c)*2)
    jr = jr[::-1]

    r = max(x[-1], l-x[0])
    for i in range(n-1):
        k = (n - i) // 2 + i
        t = 0
        if (n-i) % 2 == 0:
            t += ir[k] - ir[i]
            t += jr[k+1] + l - x[k]
        else:
            t += ir[k] - ir[i] + x[k]
            t += jr[k+1]
        if r < t:
            r = t

    x = [l-c for c in x][::-1]
    tr = ir[::-1]
    ir = jr[::-1]
    jr = tr
    for i in range(n-1):
        k = (n - i) // 2 + i
        t = 0
        if (n-i) % 2 == 0:
            t += ir[k] - ir[i]
            t += jr[k+1] + l - x[k]
        else:
            t += ir[k] - ir[i] + x[k]
            t += jr[k+1]
        if r < t:
            r = t

    return r


print(main())

Solution (Python):
from sys import stdin
from itertools import repeat
def main():
    L, n = map(int, stdin.readline().split())
    a = map(int, stdin.read().split(), repeat(10, n))
    sr = [0] * (n + 1)
    sl = [0] * (n + 1)
    for i in xrange(n):
        sl[i+1] = sl[i] + a[i]
    for i in xrange(n - 1, 0, -1):
        sr[i-1] = sr[i] + L - a[i]
    ans = 0
    for i in xrange(n):
        l = i
        r = n - 1 - i
        if l < r:
            r = l + 1
        else:
            l = r
        t = (sr[i] - sr[i+r] + sl[i] - sl[i-l]) * 2 + a[i]
        if ans < t:
            ans = t
    for i in xrange(n - 1, -1, -1):
        l = i
        r = n - 1 - i
        if l > r:
            l = r + 1
        else:
            r = l
        t = (sr[i] - sr[i+r] + sl[i] - sl[i-l]) * 2 + L - a[i]
        if ans < t:
            ans = t
    print ans
main()