Minimum Water Required for Non-decreasing Water Distribution

You are given n plants in a row. Each plant has a height given by an array heights of length n. You must water each plant such that:

• The water allocated to a plant is at least equal to its height.
• The water distribution is non-decreasing from left to right; that is, if w[i] represents the water given to the i^th plant, then \(w[1] \leq w[2] \leq \cdots \leq w[n]\).

Your task is to determine the minimum total amount of water required to water all plants meeting the above criteria.

Note: The water given to the first plant is exactly its height, and for any plant i (i > 1), we assign \(w[i] = \max(heights[i], w[i-1])\). The answer is \(\sum_{i=1}^n w[i]\).

inputFormat

The input is given from standard input in the following format:

N
h1 h2 h3 ... hN

Here, N is the number of plants, and h1, h2, ..., hN are their respective heights.

outputFormat

Output the minimum total amount of water required on a single line. The output should be written to standard output.

5
2 4 3 5 2

20