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):
import sys

input=sys.stdin.readline

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

accu1=[X[i] for i in range(N)]
accu2=[X[i] for i in range(N)]
for i in range(1,N):
    accu1[i]+=accu1[i-1]
for i in range(N-2,-1,-1):
    accu2[i]+=accu2[i+1]

ans=max(L-X[0],X[-1])
for i in range(1,N):
    j=N-i
    test=0
    if i<j:
        test1=2*accu1[i-1]-X[i-1]+2*i*L-2*(accu1[2*i-1]-accu1[i-1])
        test2=2*accu1[i-1]+2*(i+1)*L-2*(accu1[2*i]-accu1[i-1])-(L-X[i])
        ans=max(test1,test2,ans)
        
        
    elif j<i:
        test1=2*L*j-2*accu2[-j]-(L-X[-j])+2*(accu2[-2*j]-accu2[-j])
        test2=2*L*j-2*accu2[-j]+2*(accu2[-2*j-1]-accu2[-j])-X[-j-1]
        
        ans=max(test1,test2,ans)
        
        
    else:
        test1=2*accu1[i-1]+2*i*L-2*(accu1[2*i-1]-accu1[i-1])-min(X[i-1],L-X[i])
        
        ans=max(ans,test1)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

def solve(A):
    if len(A) == 1:
        return A[0]
    S = [None]*N
    s = 0
    for i, a in enumerate(A):
        s += a
        S[i] = s

    T = [None]*N
    t = 0
    for i in reversed(range(N)):
        t += (L-A[i])
        T[i] = t

    ans = 0
    for i in range(N-1):
        if 2*i+3 < N:
            ans = max(ans, 2*S[i]+2*(T[i+1]-T[2*i+3])-(L-A[i+1]))
        elif 2*i+2 > N:
            ans = max(ans, 2*(S[i]-S[2*i-N+1]) + 2*T[i+1] - (L-A[i+1]))
        else:
            ans = max(ans, 2*S[i]+2*T[i+1]-(L-A[i+1]))
    return ans

a1 = solve(A)
a2 = solve([L-a for a in reversed(A)])
print(max(a1, a2))

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc030/tasks/agc030_b

列の左右からとっていく。
移動距離は、連続して同じ方からとった場合と前とは別方向からとった場合で異なる

1.連続してとった場合は、単純に前に取った要素との差が加わる
2.そうでない場合は、原点と前の要素の距離+原点と今回の要素の距離が加わる

左右で撮る場所を決めてしまった場合はどう？
同じ要素を取る場合、1を選んだ時の加算 < 2を選んだ時の加算は確定

多い方では、必ず1をその差分だけ？選ばなくてはいけない
2を選んだ方が得な要素は？

前に何を選んだかによらず、寄与を考える方法を考案する必要がある
2つの山には分けておこう。

なるべく後半に反対の山からもらう方が寄与が大きいのは当然。
よって、まず多い方の山を少ない方と同数にして、交互に行き来すれば最適？
→O(N**2)なので部分点か？

→ここから高速化 or 更に探索空間を減らせないか考える

累積和で高速化可能か？
→とりあえず部分点狙ってみよう

l==rのとき、lの右端 と rの左端のうち最小以外は全て2こ取れる
l>rのとき、lのr個と、rは2回取れる +　lのr+1を1回取れる
r<lの時は逆

dpで解けるのか？
"""

L,N = map(int,input().split())

X = []

dl = []
dr = []

for i in range(N):

    x = int(input())
    dl.append(x)
    dr.append(L-x)

dls = [0]
drs = [0]

for i in range(N):

    dls.append(dls[-1] + dl[i])
    drs.append(drs[-1] + dr[-1-i])

ans = 0
for l in range(N+1):

    r = N-l
    if l==r:
        ans = max( ans , 2 * (dls[l] + drs[r]) - min(dl[l-1],dr[l]) )
    elif l > r:

        

        lsum = 2 * (dls[l] - dls[l-(r+1)]) - dl[l-1]
        rsum = 2 *  drs[r]

        ans = max(ans , lsum + rsum)

        

        lsum = 2 * (dls[l] - dls[l-r])
        rsum = 2 * (drs[r]) - dr[-1*r]

        ans = max(ans , lsum + rsum)
    else:

        

        rsum = 2 * (drs[r] - drs[r-(l+1)]) - dr[-1*r]
        lsum = 2 * (dls[l])

        ans = max(ans , lsum + rsum)

        

        rsum = 2 * (drs[r] - drs[r-l])
        lsum = 2 * (dls[l]) - dl[l-1]

        ans = max(ans , lsum + rsum)

print (ans)

Solution (Python):
from itertools import accumulate

L, N, *X = map(int, open(0).read().split())

Y = [L - x for x in reversed(X)]

Sx = [0] + list(accumulate(X))
Sy = [0] + list(accumulate(Y))

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

    x = X[i] + 2 * (Sx[i] - Sx[i - mi]) + 2 * (Sy[j] - Sy[j - mi - int(i < j)])
    y = Y[j] + 2 * (Sx[i] - Sx[i - mi - int(i > j)]) + 2 * (Sy[j] - Sy[j - mi])
    ans = max(ans, x, y)

print(ans)

Solution (Python):
L, N = map(int, raw_input().split())
X = [input() for _ in range(N)]

def f(T):
  n = len(T)
  S = [0]*(2*n+1)
  for i in range(2*n):
    S[i+1] = S[i]+T[i%n]
  a = S[n-1]
  ans = a
  for i in range(n-2):
    a += 2*(S[2*n-i*2-3]-S[n-i-1])
    a -= 2*(S[2*n-i-2]-S[2*n-i*2-2])
    a -= T[n-i-2]
    ans = max(ans, a)
  return ans

A = [X[0]]+[X[i+1]-X[i] for i in range(N-1)]+[L-X[-1]]
print max(f(A), f(A[::-1]))

Solution (Python):
import sys
readline = sys.stdin.readline

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

Acl = X[:]
for i in range(1, N):
    Acl[i] += Acl[i-1]

Acl += [0]

Acr = [L-x for x in X]
for i in range(N-2, -1, -1):
    Acr[i] += Acr[i+1]

Acr += [0]

res = max(L-X[0], X[-1])

for i in range(N):
    k = min(i+1, N-1-i)
    if i+1 == N-1-i:
        res = max(res, 2*(Acr[i+1] + Acl[i]) - X[i])
    elif i+1 < N-1-i:
        res = max(res, 2*(Acr[i+1] - Acr[i+1+k] + Acl[i]) - X[i])
    else:
        res = max(res, 2*(Acr[i+1] + Acl[i] - Acl[i-k-1]) - X[i])
    
    k = min(i, N-i)
    if i == N-i:
        res = max(res, 2*(Acr[i] + Acl[i-1]) - L + X[i])
    elif i < N-i:
        res = max(res, 2*(Acr[i] - Acr[i+k+1] + Acl[i-1]) - L + X[i])
    else:
        res = max(res, 2*(Acr[i] + Acl[i-1] - Acl[i-1-k]) - L + X[i])
print(res)

Solution (Python):
L,N=map(int,input().split())
X=[int(input()) for i in range(N)]
X=[0]+X
Y=[0]
for i in range(N,0,-1):
    Y.append(L-X[i])
sum_X=[0]*(N+1)
sum_Y=[0]*(N+1)
for i in range(1,N+1):
    sum_X[i]=X[i]+sum_X[i-1]
    sum_Y[i]=Y[i]+sum_Y[i-1]
ans=0
for i in range(N//2+1,N+1):
    j=N-i
    num_1=2*(sum_Y[j]+sum_X[i]-sum_X[i-j])-Y[j]
    if i!=j:
        num_2=2*(sum_Y[j]+sum_X[i]-sum_X[i-j-1])-X[i]
    ans=max(ans,num_1,num_2)
X,Y=Y[:],X[:]
sum_X,sum_Y=sum_Y[:],sum_X[:]
for i in range(N//2+1,N+1):
    j=N-i
    num_1=2*(sum_Y[j]+sum_X[i]-sum_X[i-j])-Y[j]
    if i!=j:
        num_2=2*(sum_Y[j]+sum_X[i]-sum_X[i-j-1])-X[i]
    ans=max(ans,num_1,num_2)
if N%2==0:
    num_1=2*(sum_X[N//2]+sum_Y[N//2])-X[N//2]
    num_2=2*(sum_X[N//2]+sum_Y[N//2])-Y[N//2]
    ans=max(ans,num_1,num_2)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

L,N=map(int,input().split())
X=[0]+[int(input()) for i in range(N)]

S=[]

for i in range(N):
    S.append(X[i+1]-X[i])
S.append(L-X[-1])



DIS=L-S[-1]
ANS=L-S[-1]
MINUS=0
PLUS=L-S[-1]



for i in range(N-1):
    if i%2==0:
        MINUS+=S[-i-2]
        PLUS+=S[-i//2-1]-S[-i-2]

    else:
        MINUS+=S[-i-2]-S[-i-1+i//2]
        PLUS-=S[-i-2]

    DIS+=PLUS-MINUS

    if ANS<DIS:
        ANS=DIS

    

S=S[::-1]

DIS=L-S[-1]
MINUS=0
PLUS=L-S[-1]



for i in range(N-1):
    if i%2==0:
        MINUS+=S[-i-2]
        PLUS+=S[-i//2-1]-S[-i-2]

    else:
        MINUS+=S[-i-2]-S[-i-1+i//2]
        PLUS-=S[-i-2]

    DIS+=PLUS-MINUS

    if ANS<DIS:
        ANS=DIS

    

print(ANS)

Solution (Python):
import sys
input = sys.stdin.readline

import numpy as np

L,N = map(int,input().split())
X = np.array([input() for _ in range(N)], dtype=np.int64)

def F(X):
    max_cost = L-X[0]
    
    Xcum = X.cumsum()
    
    M = N//2
    if M > 0:
        arr = 4*Xcum[:M] + 2*L*np.arange(1,M+1) - 2*Xcum[1:2*M+1:2] - X[:M]
        max_cost = max(max_cost, arr.max())
    
    M = (N-1)//2
    if M > 0:
        arr = (Xcum[:M] + L*np.arange(1,M+1) - Xcum[2:M+M+2:2] + Xcum[1:M+1])*2 - X[1:M+1] + L
        max_cost = max(max_cost,arr.max())
    return max_cost

answer = max(F(X), F(L-X[::-1]))
print(answer)

Solution (Python):
l, n = [int(item) for item in input().split()]
right = []
left = []
for i in range(n):
    a = int(input())
    right.append(a)
    left.append(l - a)
left.reverse()

rsum = [0] * (n+1)
lsum = [0] * (n+1)
for i in range(n):
    rsum[i+1] += rsum[i] + right[i]
    lsum[i+1] += lsum[i] + left[i]


ans = max(right[-1], left[-1])


for i in range(n-1):
    val = left[i] * 2
    rest = n - (i + 1)
    val += rsum[(rest + 1) // 2] * 2
    val += (lsum[rest // 2 + i + 1] - lsum[i + 1]) * 2
    if rest % 2 == 0:
        val -= left[rest // 2 + i]
    else:
        val -= right[(rest + 1) // 2 - 1]
    ans = max(ans, val)


for i in range(n-1):
    val = right[i] * 2
    rest = n - (i + 1)
    val += lsum[(rest + 1) // 2] * 2
    val += (rsum[rest // 2 + i + 1] - rsum[i + 1]) * 2
    if rest % 2 == 0:
        val -= right[rest // 2 + i]
    else:
        val -= left[(rest + 1) // 2 - 1]
    ans = max(ans, val)
print(ans)

Solution (Python):
def calc(l,n,arr):
  cum1=[0]
  cum2=[0]
  for i in range(n):
    cum1.append(cum1[-1]+arr[i])
  for i in range(n-1,-1,-1):
    cum2.append(cum2[-1]+(l-arr[i]))
  ans=0
  for i in range(n):
    if (n-i-1)%2==0:
      lm=(n-i-1)//2
      rm=(n-i-1)//2
      end=i+rm
      tmp=2*(cum1[rm+i]-cum1[i])+2*cum2[lm]+arr[end]
    else:
      lm=(n-i-1)//2+1
      rm=(n-i-1)//2
      end=n-lm
      tmp=2*(cum1[rm+i+1]-cum1[i])+2*cum2[lm-1]+(l-arr[end])
    ans=max(ans,tmp)
  return ans

l,n=map(int,input().split())
arr=[int(input()) for _ in range(n)]
ans1=calc(l,n,arr)
for i in range(n):
  arr[i]-=l
  arr[i]*=-1
ans2=calc(l,n,arr[::-1])
print(max(ans1,ans2))

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

def clockwise(X, Y):
    cum_X = [0 for _ in range(N+1)]
    cum_Y = [0 for _ in range(N+1)]
    for i in range(1, N+1):
        cum_X[i] = X[i-1] + cum_X[i-1]
        cum_Y[i] = Y[i-1] + cum_Y[i-1]
    d = 0
    for i in range(N):
        x_last = (N-i-1) // 2
        y_last = N-i-1-x_last
        if (N-i) % 2 == 0:
            last = Y[y_last-1]
        else:
            last = X[i+x_last]
        d = max(d, 2*(X[i]+cum_X[i+x_last+1]-cum_X[i+1]+cum_Y[y_last])-last)
    return d

ans = max(clockwise(X, Y), clockwise(Y, X))
print(ans)

Solution (Python):
l, n = [int(i) for i in input().split(" ")]
x = []

for i in range(0, n):
    x.append(int(input()))

y = [l - x[n - i - 1] for i in range(0, n)]
m = 0

def cal(x, y):
    global m
    
    sx = [0] * (n + 1)
    sy = [0] * (n + 1)
    for i in range(1, n + 1):
        sx[i] = sx[i - 1] + x[i - 1]
        sy[i] = sy[i - 1] + y[i - 1]
    for i in range(0, n):
        xc = (n - i - 1) // 2
        yc = (n - i - 1) - xc
        last = 0
        if (n - i) % 2 == 0:
            last = y[yc - 1]
        else:
            last = x[i + xc]
        mt = 2 * x[i] + 2 * (sy[yc] + sx[i + xc + 1] - sx[i + 1]) - last
        
        if mt > m:
            m = mt

cal(x, y)
cal(y, x)
print(m)

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



 
''' Start at X[0] '''
''' In the case when turn first '''
ans0 = X[0]

i = 0
j = N-1
direc = 1 
while i!=j:
    direc *= -1
    ans0 += L+X[i]-X[j]
    if direc==-1:
        i += 1
    elif direc==1:
        j -= 1
if N%2==0:
    i = N//2
    j = N//2
else:
    i = N//2
    j = N//2+1
tmp_ans = ans0
for k in range(N-1):
    tmp_ans += -L-2*X[k]+X[i]+X[j]
    if i==j:
        j += 1
    else:
        i += 1
    ans0 = max(ans0, tmp_ans)
 
 
''' Start at X[N-1] '''
''' In the case when turn first '''
ans1 = L-X[N-1]
i = 0
j = N-1
direc = -1 
while i!=j:
    direc *= -1
    ans1 += L+X[i]-X[j]
    if direc==-1:
        i += 1
    elif direc==1:
        j -= 1
if N%2==0:
    i = (N-2)//2
    j = (N-2)//2
else:
    i = (N-2)//2
    j = (N-2)//2+1
tmp_ans = ans1
for k in reversed(range(1, N)):
    tmp_ans += -L+2*X[k]-X[i]-X[j]
    if i==j:
        i -= 1
    else:
        j -= 1
    ans1 = max(ans1, tmp_ans)
 
print(max(ans0, ans1))

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

ans0 = X[0]

i = 0
j = N-1
direc = 1 
while i!=j:
    direc *= -1
    ans0 += L+X[i]-X[j]
    if direc==-1:
        i += 1
    elif direc==1:
        j -= 1
if N%2==0:
    i = N//2
    j = N//2
else:
    i = N//2
    j = N//2+1
tmp_ans = ans0
for k in range(N-1):
    tmp_ans += -L-2*X[k]+X[i]+X[j]
    if i==j:
        j += 1
    else:
        i += 1
    ans0 = max(ans0, tmp_ans)
 
 
''' Start at X[N-1] '''
''' In the case when turn first '''
ans1 = L-X[N-1]
i = 0
j = N-1
direc = -1 
while i!=j:
    direc *= -1
    ans1 += L+X[i]-X[j]
    if direc==-1:
        i += 1
    elif direc==1:
        j -= 1
if N%2==0:
    i = (N-2)//2
    j = (N-2)//2
else:
    i = (N-2)//2
    j = (N-2)//2+1
tmp_ans = ans1
for k in reversed(range(1, N)):
    tmp_ans += -L+2*X[k]-X[i]-X[j]
    if i==j:
        i -= 1
    else:
        j -= 1
    ans1 = max(ans1, tmp_ans)
 
print(max(ans0, ans1))

Solution (Python):
ln, kn, *ki = map(int, open(0).read().split())

pa = ki[-1]
ky = [pa]
kigu = 1
for ys in range(2, kn + 1):
    
    if kigu == 1:
        pa += ki[kn - ys] * 2 + ln - ki[-(ys // 2)] * 2
    
    else:
        pa += ki[kn - ys] * 2 - ki[-(ys // 2) - 1] + ln - ki[-(ys // 2)]
    ky.append(pa)
    kigu *= -1


pa = ln - ki[0]
ky.append(pa)
kigu = 1
for ys in range(2, kn + 1):
    
    if kigu == 1:
        pa += (ln-ki[ys - 1]) * 2 - ln + ki[ys // 2 - 1] * 2
    
    else:
        pa += (ln-ki[ys - 1]) * 2+ki[ys//2]-ln+ki[ys//2-1]
    ky.append(pa)
    kigu *= -1

print(max(ky))

Solution (Python):
import sys
from collections import deque
l,n=map(int,input().split())
c=n
tree1=[int(i) for i in sys.stdin]
reversed_tree1=[l-i for i in reversed(tree1)]
tree=deque(tree1)
reversed_tree=deque(reversed_tree1)
if n%2 == 0:
  ans= sum(tree1)*2 + l*(n-1) +tree1[n//2] - sum(tree1[n//2:])*4
  ans2= sum(reversed_tree1)*2 + l*(n-1) +reversed_tree1[n//2] - sum(reversed_tree1[n//2:])*4
  n-=1
  c-=1
  ans3= ans-tree.popleft()*2-l+tree[n//2]*2
  ans= max(ans,ans3)
  ans4= ans2-reversed_tree.popleft()*2-l+(reversed_tree[n//2])*2
  ans2= max(ans2,ans4)
else:
  ans= sum(tree1)*2 + l*(n-1) - tree1[n//2] - sum(tree1[((n//2)+1):])*4
  ans3=ans
  ans2= sum(reversed_tree1)*2 + l*(n-1) - reversed_tree1[n//2] - sum(reversed_tree1[((n//2)+1):])*4
  ans4=ans2
for i in range(n//2):
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[(n-1)//2]+tree[(n+1)//2]
  ans= max(ans_stack,ans)
  ans3=ans_stack
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[n//2]*2
  ans=max(ans_stack,ans)
  ans3=ans_stack
n=c
for i in range(n//2):
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[(n-1)//2]+reversed_tree[(n+1)//2]
  ans2=max(ans_stack,ans2)
  ans4=ans_stack
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[n//2]*2
  ans2=max(ans2,ans_stack)
  ans4=ans_stack
print(max(ans,ans2))

Solution (Python):
import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
X2 = L - X[::-1]
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]
Z = np.concatenate((np.arange(N, -1, -2), np.arange(N - 1, -1, -2)[::-1]))


def myfunc(n, x):
    return x[n + (N - n + 1)//2 - 1] - 2 * x[n - 1] - (L - x[N - (N - n + 1)//2])


len1 = np.dot(Z, Y1)
len2 = np.dot(Z, Y2)
x1 = X.tolist()
x2 = X2.tolist()
ans = max(len1, len2)
for n in range(1, (N + 1) // 2):
    len1 += myfunc(n, x1)
    len2 += myfunc(n, x2)
    ans = max(ans, len1, len2)

print(ans)

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

RL = [0]
RSL = [0]
for i in X:
  RL.append(i)
  RSL.append(RSL[-1] + i)

LL = [0]
LSL = [0]
for i in X[::-1]:
  LL.append(L - i)
  LSL.append(LSL[-1] + (L - i))

D = [RSL[i] + LSL[N - i] for i in range(N + 1)]

Ans = max(RL[N], LL[N])
for i in range(1, N):
  if i < (N + 1) // 2:
    k = N - 2 * i
    t = (D[i] - LSL[max(k - 1, 0)]) * 2  - LL[N - i]
    s = (D[i] - LSL[k]) * 2  - RL[i]
    Ans = max(Ans, t, s)
  else:
    k = 2 * i - N
    t = (D[i] - RSL[max(k - 1, 0)]) * 2  - RL[i]
    s = (D[i] - RSL[k]) * 2  - LL[N - i]
    Ans = max(Ans, t, s)
  
print(Ans)

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

Y = [0]*(N+1)
for i in range(N):
    Y[i+1] = X[i] + Y[i]

ans = max(X[N-1], L - X[0])
for i in range(N-1):
    P = i+1; Q = N - (i+1)
    if P < Q:
        ans = max(ans, 2*Y[i+1] + 2*(L*(P+1) - (Y[i+P+2] - Y[i+1])) - (L - X[i+1]))
    elif P > Q:
        ans = max(ans, 2*(Y[i+1] - Y[i-Q]) - X[i] + 2*(L*Q - (Y[N] - Y[i+1])))
    K = min(P, Q)
    ans = max(ans, 2*(Y[i+1] - Y[i+1-K]) + 2*(L*K - (Y[i+K+1] - Y[i+1])) - min(X[i], L-X[i+1]))
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 sys
from itertools import accumulate

circumference, n = map(int, input().split())
lll = list(map(int, sys.stdin.readlines()))
rrr = [circumference - l for l in lll]
rrr.reverse()
lll = [0] + lll
rrr = [0] + rrr
acc_l = list(accumulate(lll))
acc_r = list(accumulate(rrr))

ans = max(lll[-1], rrr[-1])
for take_l in range(1, n):
    take_r = n - take_l

    
    tmp_l = lll[take_l] + 2 * (acc_l[take_l - 1] + acc_r[take_r])
    
    tmp_r = rrr[take_r] + 2 * (acc_r[take_r - 1] + acc_l[take_l])

    if take_l < take_r:
        tmp_l -= 2 * acc_r[take_r - take_l]
        tmp_r -= 2 * acc_r[take_r - 1 - take_l]
    elif take_l > take_r:
        tmp_l -= 2 * acc_l[take_l - 1 - take_r]
        tmp_r -= 2 * acc_l[take_l - take_r]

    ans = max(ans, tmp_l, tmp_r)
print(ans)

Solution (Python):
L,n = (int(i) for i in input().split())
x = [int(input()) for i in range(n)]
t,t2,y,a = [0],[0],[],0
for i in range(n):
	t.append(t[-1]+x[i])
	t2.append(L+t2[-1]-x[n-i-1])
	y.append(L-x[n-i-1])
for i in range(n):
	if (n-i-1)%2: a = max(a,y[(n-i-1)//2]+2*(t[i+(n-i-1)//2+1]-t[i]+t2[(n-i-1)//2]))
	else: a = max(a,2*(t[i+(n-i-1)//2+1]-t[i]+t2[(n-i-1)//2])-x[i+(n-i-1)//2])
for i in range(n):
	if (n-i-1)%2: a = max(a,x[(n-i-1)//2]+2*(t2[i+(n-i-1)//2+1]-t2[i]+t[(n-i-1)//2]))
	else: a = max(a,2*(t2[i+(n-i-1)//2+1]-t2[i]+t[(n-i-1)//2])-y[i+(n-i-1)//2])
print(a)

Solution (Python):
def run(L, N, X):
    '''
    最初に向きを変える点をsとする
    その後は向きを変えながら最後の点まで行けばよい
    最後の点をfとする
    ある点をiと置く
    0からiの左回りの距離をli, 右回りの距離をriと置くと
    全体の距離は2*liのsからfの和と2*riのNからfの和を加算し
    最後の回りが左回りなら上記からlf+2*rfを減算し、
    右回りなら2*lf+rfを減算すれば全体の距離がでる
    sを1からfの場合すべてを求め、その最大値を出力すればよい
    ただし最初の回る方向が右と左両方を求める必要がある
    累積和を使えば、2*liのsからfの和をO(1)で求められる
    '''
    
    l_sum = {0: 0}
    r_sum = {N+1: 0}
    for i in range(1, N+1):
        l_sum[i] = l_sum[i-1] + X[i-1]
    for i in range(N, 0, -1):
        r_sum[i] = r_sum[i+1] + L - X[i-1]
    
    ret = 0
    for s in range(1, N+1):
        
        nodes = (N - s + 1)
        
        f = int(s + (nodes - (nodes % 2)) / 2)
        if nodes % 2 == 1:
            last_dir_l = True
        else:
            last_dir_l = False
        if last_dir_l:
            tmp = 2*(l_sum[f] - l_sum[s-1]) + 2*(r_sum[f+1]) - X[f-1]
        else:
            tmp = 2*(l_sum[f-1] - l_sum[s-1]) + 2*(r_sum[f]) - (L - X[f-1])
        ret = max(ret, tmp)

    
    for s in range(1, N+1):
        
        nodes = s
        
        f = int((nodes + (nodes % 2)) / 2)
        if nodes % 2 == 1:
            last_dir_r = True
        else:
            last_dir_r = False
        if last_dir_r:
            tmp = 2*(l_sum[f-1]) + 2*(r_sum[f] - r_sum[s+1]) - (L - X[f-1])
        else:
            tmp = 2*(l_sum[f]) + 2*(r_sum[f+1] - r_sum[s+1]) - X[f-1]
        ret = max(ret, tmp)
    return ret


def main():
    L, N = map(int, input().split())
    X = []
    for _ in range(N):
        X.append(int(input()))
    print(run(L, N, X))


if __name__ == '__main__':
    main()

Solution (Python):
def is_even(num):
    return num % 2 == 0
def goback(M, x, Sx):
    k = M // 2
    if M == 0:
        return L - x[0]
    elif M == 1:
        return 2 * (L - x[1]) + x[0]
    elif is_even(M):
        return 2 * Sx[k - 1] - 2 * (Sx[M] - Sx[M - k]) - x[M - k] + L * (2 * k + 1)
    else:
        return 2 * Sx[k - 1] + x[k] - 2 * (Sx[M] - Sx[M - k - 1]) + L * 2 * (k + 1)

L, N = (int(i) for i in input().split())
ans = 0

pl = []
for i in range(N):
    pl.append(int(input()))
sumpl = [pl[0]]
for i in range(1, N):
    sumpl.append(sumpl[i - 1] + pl[i])
for i in range(0, N):
    ans = max(ans, goback(i, pl, sumpl))

revpl = [L - p for p in pl[::-1]]
sumrevpl = [revpl[0]]
for i in range(1, N):
    sumrevpl.append(sumrevpl[i - 1] + revpl[i])
for i in range(0, N):
    ans = max(ans, goback(i, revpl, sumrevpl))

print(ans)

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

ans=0
for i in range(N):
  a=2*X[i]
  d=(N-i-1)//2
  if (N-i)%2:
    a+=2*(S[i+d+1]-S[i+1])
    a+=2*(L*d-(S[N]-S[N-d]))
    a-=X[i+d]
  else:
    a+=2*(S[i+d+1]-S[i+1])
    a+=2*(L*(d+1)-(S[N]-S[N-d-1]))
    a-=L-X[N-d-1]
  ans=max(ans,a)
X_new=[]
S_new=[0]
for x in X[::-1]:
  X_new.append(L-x)
  S_new.append(S_new[-1]+L-x)

for i in range(N):
  a=2*X_new[i]
  d=(N-i-1)//2
  if (N-i)%2:
    a+=2*(S_new[i+d+1]-S_new[i+1])
    a+=2*(L*d-(S_new[N]-S_new[N-d]))
    a-=X_new[i+d]
  else:
    a+=2*(S_new[i+d+1]-S_new[i+1])
    a+=2*(L*(d+1)-(S_new[N]-S_new[N-d-1]))
    a-=L-X_new[N-d-1]
  ans=max(ans,a)
print(ans)

Solution (Python):
L, N = map(int, input().split())
X = [0]
for _ in range(N):
    X.append(int(input()))

s = [0] * (N + 1)
t = [0] * (N + 1)
for i in range(1, N + 1):
    s[i] = s[i-1] + X[i]
    t[i] = t[i-1] + (L - X[N - i + 1])
Y = [0] + [L - X[N - i] for i in range(N)]




def get_d(s, x, i):
    if i == N:
        return x[N]
    a = i + (N - i) // 2
    return (
        2 * (s[a] - s[i-1] + L * (N - a) - s[N] + s[a]) -
        (x[a] if (N - i) % 2 == 0 else (L - x[a + 1]))
    )


ans = 0
for i in range(1, N + 1):
    ans = max(ans, get_d(s, X, i), get_d(t, Y, i))

print(ans)

Solution (Python):
from itertools import accumulate

def burn(L, l_x):
    l_x.append(L)
    l_x.insert(0, 0)
    r_x = list(L - i for i in reversed(l_x))
    return max(burn_in(L, l_x, r_x), burn_in(L, r_x, l_x))


def burn_in(L, l_x, l_l):
    r_x = list(L - i for i in reversed(l_x))
    l = list(accumulate(l_x))
    r = list(accumulate(r_x))
    n_max = len(l_x)
    ret = 0
    for i in range(n_max - 2):
        n_r = (n_max - 2 - i) // 2
        n_l = n_max - n_r - 2
        res = l_x[n_l] if (n_max - i) % 2 == 1 else r_x[n_r]
        can = (l[n_l] - l[i] + r[n_r]) * 2 - res
        ret = max(ret, can)
    return ret


def main():
    L, N = map(int, input().split())
    x = [int(input()) for _ in range(N)]
    print(burn(L, x))
    
if __name__ == "__main__":
    main()

Solution (Python):
import math

L, N = (int(i) for i in input().split())
X = [int(input()) for _ in range(N)]
X.insert(0, 0)

X_r = [L - i for i in reversed(X)]
X_r.insert(0, 0)
X_r.pop()

def lsum(l):
    s = 0
    for i in l:
        s += i
        yield s

X_sum = list(lsum(X))
X_r_sum = list(lsum(X_r))

def f_l(p, n):
    N_tmp = N - n
    a = N_tmp // 2
    if N_tmp == 0:
        return 0
    elif N_tmp % 2 == 0:
        return 2 * X_sum[a] + X_r_sum[a + n] + X_r_sum[a + n - 1] - 2 * X_r_sum[n] + p
    else:
        return X_sum[a+1] + X_sum[a] + 2 * X_r_sum[a + n] - 2 * X_r_sum[n] + p


def f_r(p, n):
    N_tmp = N - n
    a = N_tmp // 2
    if N_tmp == 0:
        return 0
    elif N_tmp % 2 == 0:
        return 2 * X_r_sum[a] + X_sum[a + n] + X_sum[a + n - 1] - 2 * X_sum[n] + p
    else:
        return X_r_sum[a+1] + X_r_sum[a] + 2 * X_sum[a + n] - 2 * X_sum[n] + p

max_l = max(X[i] + f_r(X[i], i) for i in range(1, N+1))
max_r = max(X_r[i] + f_l(X_r[i], i) for i in range(1, N+1))

print(max(max_l, max_r))

Solution (Python):
L, N = [int(_) for _ in input().split()]
X = [int(input()) for _ in range(N)]


def calc(X):
    cumsum = [0]
    for x in X:
        cumsum += [cumsum[-1] + x]
    res = 0
    for i in range(N):
        if (i + N) % 2:
            end = (i + N - 1) // 2
            d = 2 * (cumsum[end + 1] - cumsum[i]) + 2 * L * (
                N - 1 - end) - 2 * (cumsum[N] - cumsum[end + 1]) - X[end]
        else:
            end = (i + N) // 2
            d = 2 * (cumsum[end] - cumsum[i]) + 2 * L * (N - end) - 2 * (
                cumsum[N] - cumsum[end]) - (L - X[end])
        res = max(res, d)
    return res


print(max(calc(X), calc([L - x for x in X[::-1]])))

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



ans = 0
for b in range(N+1):
    z = sumL[b] + sumR[b+1]
    if(b > 0):
        if(b <= N-b):
            ans = max(ans, z+sumL[b-1]+sumR[b+1]-2*sumR[N+1-(N-b-b)])
            
        else:
            ans = max(ans, z+sumL[b-1]+sumR[b+1]-2*sumL[b-(N-b)-1])
            
    if(b < N):
        if(b >= N-b):
            ans = max(ans, z+sumL[b]+sumR[b+2]-2*sumL[b-(N-b)])
            
            
        else:
            ans = max(ans, z+sumL[b]+sumR[b+2]-2*sumR[N+1-(N-b-b)+1])
            
    
print(ans)

Solution (Python):
import math
L, N = map(int, input().split())
X = [None for i in range(N)]
DistAntiClock, DistClock = [0 for i in range(N+1)], [0 for i in range(N+1)]
for i in range(N):
    X[i] = int(input())
    DistAntiClock[i+1] = DistAntiClock[i] + 2 * X[i]
for i in range(N):
    DistClock[i+1] = DistClock[i] + (L - X[-1-i]) * 2

maxLength = max(X[N-1], L - X[0])
for i in range(1, N):
    finIndex = math.ceil((i + N)/2)
    if (i + N) % 2 == 0:
        AntiClockLength = DistAntiClock[finIndex] - DistAntiClock[i-1] - X[finIndex-1] + DistClock[N - finIndex] 
        ClockLength = DistClock[finIndex] - DistClock[i-1] - (L-X[-finIndex]) + DistAntiClock[N - finIndex]
    else:
        AntiClockLength = DistAntiClock[finIndex - 1] - DistAntiClock[i-1] + DistClock[N - finIndex + 1] - (L - X[finIndex - 1])
        ClockLength = DistClock[finIndex - 1] - DistClock[i-1] + DistAntiClock[N - finIndex + 1] - X[N - finIndex]
    maxLength = max(max(AntiClockLength, ClockLength), maxLength)

print(maxLength)

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

X = sorted(X)

ma = 0
for k in range(2):
    if k == 1:
        X = [L-X[-i] for i in range(1, N+1)]
    s = X[0]
    for i in range(1, N):
        if i % 2 == 1:
            s += L - X[-(i//2)-1] + X[i//2]
        else:
            s += X[i//2] + (L - X[-(i//2)])

    ma = max(ma, s)
    lt = (N-1) // 2 if N % 2 == 1 else -N//2
    for i in range(1, N):
        if lt > 0:
            if N % 2 == 1:
                s += X[lt] - X[i-1]*2 - (L - X[lt + 1])
            else:
                s += X[lt] - X[i-1] * 2 - (L - X[lt + 1])
            lt = 1 + lt - N
            ma = max(ma, s)
        else:
            if N % 2 == 1:
                s += X[lt] - X[i-1] * 2 - (L - X[lt])
            else:
                s += X[lt]*2 - L - X[i-1] * 2
            lt = N + lt
            ma = max(ma, s)

print(ma)

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

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

cum_l = [0]
for x in X:
    cum_l.append(cum_l[-1] + x)

cum_r = [0]
for x in reversed(X):
    cum_r.append(cum_r[-1] + L-x)

ans = 0
for st_l in range(1,N+1):
    m = N - st_l
    r = m - m//2
    l = st_l + m//2
    tmp = (cum_l[l] - cum_l[st_l-1] + cum_r[r]) * 2
    if m%2:
        tmp -= (L - X[-r])
    else:
        tmp -= X[l-1]
    ans = max(ans, tmp)

for st_r in range(1,N+1):
    m = N - st_r
    l = m - m//2
    r = st_r + m//2
    tmp = (cum_r[r] - cum_r[st_r-1] + cum_l[l]) * 2
    if m%2:
        tmp -= X[l-1]
    else:
        tmp -= (L - X[-r])
    ans = max(ans, tmp)

print(ans)

Solution (Python):

"""
Created on Sun Dec 30 09:04:16 2018

@author: Yamazaki Kenichi
"""
L,N = map(int, input().split(' '))
X = [int(input()) for i in range(N) ]






X = [0] + X 
temp = L - X[1]
ans =  temp

itr1 = 0
itr2 = N

a = N%2

for i in range(-(N-1),N):
    if (i+a)%2 == 1:
        itr1 += 1
    else:
        itr2 -= 1

    if X[i]-X[i-itr1] >=0:
        minus = X[i]-X[i-itr1]
    else:
        minus = L+(X[i]-X[i-itr1])

    if X[i+itr2]-X[i] >=0:
        plus = X[i+itr2]-X[i]
    else:
        plus = L+(X[i+itr2]-X[i])
    temp = temp - minus + plus

    ans = max(ans,temp)
print(ans)

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





''' Start at X[0] '''
''' In the case when turn first '''
ans0 = X[0]

i = 0
j = N-1
direc = 1 
while i!=j:
    direc *= -1
    ans0 += L+X[i]-X[j]
    if direc==-1:
        i += 1
    elif direc==1:
        j -= 1
if N%2==0:
    i = N//2
    j = N//2
else:
    i = N//2
    j = N//2+1
tmp_ans = ans0
for k in range(N-1):
    tmp_ans += -L-2*X[k]+X[i]+X[j]
    if i==j:
        j += 1
    else:
        i += 1
    ans0 = max(ans0, tmp_ans)


''' Start at X[N-1] '''
''' In the case when turn first '''
ans1 = L-X[N-1]
i = 0
j = N-1
direc = -1 
while i!=j:
    direc *= -1
    ans1 += L+X[i]-X[j]
    if direc==-1:
        i += 1
    elif direc==1:
        j -= 1
if N%2==0:
    i = (N-2)//2
    j = (N-2)//2
else:
    i = (N-2)//2
    j = (N-2)//2+1
tmp_ans = ans1
for k in reversed(range(1, N)):
    tmp_ans += -L+2*X[k]-X[i]-X[j]
    if i==j:
        i -= 1
    else:
        j -= 1
    ans1 = max(ans1, tmp_ans)

print(max(ans0, ans1))

















































































''' N^2 case '''