#! python3

b,p = map(int, input().split())

ds = list(map(int, input().split()))

INF = 1 << 60

def combine(dp, shift):
    ptr0 = 0
    ptr1 = 0

    last = -1
    curmin = INF
    res = []
    while ptr0 < len(dp[0]) or ptr1 < len(dp[1]):
        while ptr0 < len(dp[0]) and dp[0][ptr0][1] < last:
            ptr0 += 1
        while ptr1 < len(dp[1]) and dp[1][ptr1][1] + shift < last:
            ptr1 += 1

        cand0 = (INF, INF)
        cand1 = (INF, INF)
        if ptr0 < len(dp[0]):
            cand0 = (dp[0][ptr0][0] + b - shift, dp[0][ptr0][1])
        if ptr1 < len(dp[1]):
            cand1 = (dp[1][ptr1][0], max(0, dp[1][ptr1][1] + shift))


        if cand0[1] < cand1[1]:
            cand = cand0
            ptr0 += 1
        elif cand1[1] < cand0[1]:
            cand = cand1
            ptr1 += 1
        else:
            cand = min(cand0,cand1)
            ptr0 += 1
            ptr1 += 1

        if cand[0] < curmin:
            res.append(cand)
            curmin = cand[0]
            last = cand[1]

    return res

dp = [[(0,0)] for j in range(2)]
# (value, index)
for digit in range(p):
    ndp = [[] for j in range(2)]
    for which in range(2):
        cura = ds[digit] + 1 - which
        ndp[which] = combine(dp, cura)
    dp = ndp

print(min(map(max,dp[1])))