open System
open System.Collections.Generic

module InputUtility =
    let InputTokens = new Queue<string>()

    let EnsureInput () =
        if InputTokens.Count = 0 then
            let input = Console.ReadLine ()
            let s = input.Split ([|' '|], StringSplitOptions.RemoveEmptyEntries)
            if s.Length > 0 then
                for x in s do InputTokens.Enqueue(x)
                true
            else false
        else true

    let rec ReadNext () =
        if EnsureInput () then InputTokens.Dequeue ()
        else ReadNext ()

    let ReadNextInt () = ReadNext () |> int

    let Read2Int () = ReadNextInt (), ReadNextInt ()

    let Read3Int () = ReadNextInt (), ReadNextInt (), ReadNextInt ()

    let ReadListOf f n =
        let rec loop acc = function
            | 0 -> List.rev acc
            | c -> loop ((ReadNext () |> f) :: acc) (c-1)
        loop [] n

    let MultipleCaseWithId f =
        let caseNum = ReadNextInt ()
        let rec loop index =
            if index = caseNum then ()
            else
                f index
                loop (index + 1)
        loop 0

    let MultipleCase f = MultipleCaseWithId (fun _ -> f ())

    let ReadList n =
        let rec loop acc = function
            | 0 -> List.rev acc
            | c -> loop (ReadNext () :: acc) (c-1)
        loop [] n

open InputUtility

module ARC077 =
    let private Guruguru () =
        let n, m = Read2Int ()
        let ps = Array.create (m + 1) (0, 0)
        let ns = Array.create (m + 1) (0, 0)
        let rec add b s t =
            if s > t then
                add b s m + add (b + m - s + 1) 1 t
            elif b < 2 then
                if s = t then 1
                else 1 + add (b + 1) (s + 1) t
            else
                let d = t - s + 1
                let nb = b - 1
                let mx, my = ps.[s]
                ps.[s] <- mx + 1, my + nb - 1
                let nx, ny = ns.[t]
                ns.[t] <- nx + 1, ny + nb + d - 1
                //printfn "%d,%A %d,%A => %d" s ps.[s] t ns.[t] d
                d
        let rec read i s p =
            if i = n then s
            else
                let q = ReadNextInt ()
                let ns = s + add 0 p q - 1
                read (i + 1) ns q
        let sum = ReadNextInt () |> read 1 0
        //printfn "sum = %d" sum
        let rec cal i c e r =
            if i > m then r
            else
                let mx, my = ps.[i]
                let pc = c + mx
                let pe = e + pc + my
                let nr = max pe r
                let nx, ny = ns.[i]
                let nc, ne = pc - nx, pe - ny
                //printfn "%d: %A %A => %d %d %d | %d %d %d" i ps.[i] ns.[i] pc pe nr nc ne r
                cal (i + 1) nc ne nr
        sum - cal 1 0 0 0
        |> printfn "%d"

    let Entry = Guruguru

ARC077.Entry ()