P2101 The Choice of Steins;Gate

On an unknown world line, Okabe Rintaro suddenly receives a dmail saying that a huge shift in the world line will occur, and his future self will not be able to reverse the change to return to the original world line no matter what. The reason for the shift is that his present self will soon miss a date with his assistant. He had planned a date with the assistant, but before going, because he had been delaying his rent, the landlord uncle asked him to help color a painting. However, he did not finish this task in the fastest way, which caused him to miss the date with the assistant, leading to a drastic change in the world line. Now it is time to save the world. Since Okabe is not good at drawing, he found you—who is also not good at drawing—to help him solve this problem (this is the choice of Steins;Gate). Anyway, the task of saving the world is now in your hands, and although you are not good at drawing, you can use programming to help solve this problem. A painting consists of $N$ rectangles, each with width $1$ and height $H_i$. The rectangles are arranged side by side with no gaps between adjacent rectangles. Initially, each rectangle is uncolored. You have a brush of width $1$ that can paint vertically or horizontally. Each time you use the brush, it must always remain entirely within the rectangles; that is, it cannot go outside the rectangles, and of course it cannot make turns while painting. Each brush stroke costs time $1$, which is independent of the length painted. For example, you can paint from the far left to the far right (as long as you do not go beyond the rectangles), and it still costs time $1$. Your goal is to fully color all rectangles. Please compute and output the minimum time required.

Line $1$: A positive integer $N$, the number of rectangles. Line $2$: $N$ positive integers $H_i$, where $H_i$ is the height of the $i$-th rectangle.

A single integer, the minimum time required.

Constraints - For $30\%$ of the testdata, $N \le 20$, $H_i \le 100$. - For $60\%$ of the testdata, $N \le 100$, $H_i \le 1000$. - For $100\%$ of the testdata, $N \le 5000$, $H_i \le 10^9$. Translated by ChatGPT 5