Polynomial Calculator

There is a special calculator for evaluating polynomials. It has 14 keys: the digits 0 through 9, plus +, ×, x, and =.

For example, to compute x^3 + x + 11, one possible key sequence is x, ×, x, ×, x, +, x, +, 1, 1, =. To compute x^3 + 2x^2 + 11, one possible key sequence is x, +, 2, ×, x, ×, x, +, 1, 1, =.

A normal calculator would interpret x, +, 2, ×, x, ×, x, +, 1, 1, = as x + 2x^2 + 11. This calculator has no separate memory, so each operation is applied immediately to the value currently stored in the calculator and the next value entered. With that sequence, the stored value becomes x, x + 2, x^2 + 2x, x^3 + 2x^2, and finally x^3 + 2x^2 + 11.

To keep the problem simple, the leading coefficient is always 1. Negative coefficients do not appear.

Given a polynomial, find the minimum number of key presses needed to compute it with this calculator.

The first line contains the degree N of the polynomial. (1 ≤ N ≤ 10,000)

The second line contains the coefficients of the polynomial in order from the highest-degree term to the constant term. The leading coefficient is always 1, every coefficient is nonnegative, and no coefficient exceeds 1,000,000,000.

Print the minimum number of key presses required.