题目描述

Alice 有一家公司，他手下有 $n$ 名员工，每名员工每天可以完成一项任务。

在接下来的 $m$ 天里，每天有 $a_i$ 个（ $0 \le a_i \le n$ ）任务待完成，Alice 需要在第 $i$ 天选择 $a_i$ 个员工完成这些任务。

如果一个员工连续 $t$ 天（ $t \gt 1$ ) 都在工作 （在这连续 $t$ 天之前的一天，和之后的一天都在休息），那么他在这 $t$ 天中一共会产生 $t-1$ 点疲劳值。

Alice 想安排一个优秀的上班方案，使得在这 $m$ 天内所有员工产生的疲劳值之和尽可能小。

所有员工在第 $0$ 天和第 $m+1$ 天都在休息。

输入格式

输入一行两个整数 $n,m$ 。

接下来一行输入 $m$ 个整数 $a_1,a_2,a_3,...,a_m$ 。

输出格式

输出一行一个整数，表示这 $m$ 天内所有员工产生的疲劳值之和的最小值。

输入输出样例 #1

输入 #1

4 7
1 2 3 4 3 2 1

输出 #1

8

输入输出样例 #2

输入 #2

4 8
3 1 2 1 3 0 4 0

输出 #2

0

说明/提示

对于 $30\%$ 的数据， $n,m \le 5$ 。

对于另外 $20\%$ 的数据， $n=1$ 。

对于另外 $20\%$ 的数据， $n=2$ 。

对于全部数据， $1 \le n \le 10^9,0 \le a_i \le n,1 \le m \le 10^6$ 。