Whitespace

Whitespace is a programming language whose programs consist only of spaces and line breaks. A space is written as SP and a line break as NL.

Yeongseon has a program written in Whitespace. It can be described by a sequence $L$ of length $N$: $L_i$ is the number of SP characters on line $i$, and every line ends with NL. In other words, the source code is $L_0$ copies of SP, then NL, then $L_1$ copies of SP, then NL, $\ldots$, then $L_{N-1}$ copies of SP, then NL.

Today Yeongseon wants to type the program using an editor that Hyobin made. The cursor can be placed at the start or the end of the document, or between any two adjacent characters. Moving the cursor costs no key presses.

The editor has the following 3 special keys.

• SPACE: inserts one SP at the cursor position.
• DELETE: deletes the SP immediately to the right of the cursor. It cannot be used when the character to the right is NL.
• RETURN: types one NL and then $K$ copies of SP, where $K$ is the number of SP characters on the line containing the cursor. It can be used only when the character immediately to the right of the cursor is NL. For example, if the document is SP NL SP SP NL SP SP SP NL and RETURN is pressed right before the second NL, the document becomes SP NL SP SP NL SP SP NL SP SP SP NL.

The editor currently contains a single NL. Given $L$, write a program that finds the minimum number of key presses needed to complete the source code.

The first line contains $N$. The second line contains $L_0, L_1, \ldots, L_{N-1}$, separated by spaces.

• $1 \le N \le 50$
• $0 \le L_i \le 1\,000\,000$

Print the minimum number of key presses needed to complete the source code on the first line.

In the first example, the document can be completed with 6 key presses as follows.

• NL
• SP NL
• SP SP NL
• SP SP SP NL
• SP SP SP NL SP SP SP NL
• SP SP SP NL SP SP SP NL SP SP SP NL
• SP SP SP NL SP SP NL SP SP SP NL