Background

Special for beginners, ^_^

Description

小 A 最近在玩一种游戏。总共有 N 种牌，每种牌被标号为 1..N，按照牌的标号的顺序 排好。现在第 i 种牌给定 Ai 张，每次取牌时，只能取标号连续且每种标号只能取一张，且要保证连续的标号中至少有一张牌可取。即：

标号： 1 2 3 4

牌数： 2 3 1 2

则此时第一次取的时候，4 个标号可以取走一张。剩下的牌数为：

标号： 1 2 3 4

牌数： 1 2 0 1

再取时，则只能取 1 2，或者 4 了。由此可知，要取光所有的牌，需要 4 次。 现在给定 N，及每个标号的牌的张数，求小 A 要取走所有牌的最少次数。 输入格式

Format

Input

第一行为一个整数 N。以下 N 行，每行一个整数 Ai，表示每个标号的牌的张数。

Output

小 A 取走所有牌的最少次数。

Samples

5 2 4 1 2 3

6

Limitation

样例解释：

2 4 1 2 3

1 3 0 1 2

0 2 0 1 2

0 1 0 1 2

0 0 0 1 2

0 0 0 0 1

0 0 0 0 0

1 <= N <= 100,000

0 <= a_i <= 100000