Розбір

Можна помітити, що для $k=0$, відповідь - це сума $a_1+{\sum }_i\max (0,a_i-a_{i-1})$.

Якщо $k=1$, то нам вигідно зробити так, щоб певне $a_i$ було рівне або $a_{i-1}$, або $a_{i+1}$. У такому випадку дві послідовні $a_i$ будуть однаковими, що є найб