题目描述

Aki 管理一排 $n$ 个房间，第 $i$ 个房间有非负灰尘量 $a_i$。Aki 有一台机器，可以执行如下操作： 选择 $i<j$，要求 $a_i,a_{i+1},\dots,a_{j-1}$ 全部严格大于 0，然后： $a_i\leftarrow a_i-1$，$a_j\leftarrow a_j+1$。

目标：让 $a_1=a_2=\dots=a_{n-1}=0$。求最少操作次数。

输入格式

两行：第一行 $n$；第二行 $a_1\dots a_n$

$2\le n\le 2\times10^5$，$0\le a_i\le 10^9$。

输出格式

按题意输出结果。

5
0 2 0 2 0

5