Snow Pillars Knockdown

There are n snow pillars arranged in a row. Each pillar i has a height of \(a_i\) units. You are tasked with helping little X knock down all the pillars in minimum time. The rules are as follows:

• You can only push the pillar at one of the two ends (either the leftmost or the rightmost) and you may do this an unlimited number of times. The time to manually push a pillar is equal to its current height.
• When you push a pillar (say the k-th one) manually at a cost of \(a_k\) time units, it falls in the direction of the push. Its initial potential \(p\) is set to \(a_k\). Then a chain reaction occurs in that same direction (if pushed from the left end, the pillars to its right are affected; if from the right, the pillars to its left are affected), following these rules:
• For each subsequent pillar \(j\) in that direction:
  • If \(p \ge a_j\), then the \(j\)-th pillar is knocked down and the potential is updated to \(p := a_j\).
  • If \(p < a_j\), then the \(j\)-th pillar is not completely knocked down; instead, its height is reduced by \(p\) (i.e. \(a_j \gets a_j - p\)) and the chain reaction stops immediately.
• The moving time of little X is negligible.

Your task is to compute the minimum total time required to knock down all the pillars.

Input Format: The first line contains an integer \(n\). The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), representing the heights of the snow pillars.

Output Format: Print a single integer representing the minimum total time needed to knock down all the pillars.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\) \( (1 \le n \le 10^5) \) representing the number of snow pillars.
2. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) \( (1 \le a_i \le 10^9) \) representing the heights of the snow pillars.

outputFormat

Output a single integer: the minimum total time required to knock down all the snow pillars.

sample

2
3 1

3