B - Number of Snow Shoveling Times Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は冬の間、自宅前の道路の雪かきを担当しています。

道路は N 個の区画に分かれており、左から順に区画 1, 区画 2, \ldots, 区画 N と番号が付いています。区画 i に積もっている雪の量は A_i センチメートルです。

高橋君は除雪シャベルを使って雪かきをします。1 回の雪かきでは、1 \leq l \leq r \leq N を満たす整数の組 (l, r) を 1 つ選び、区画 l から区画 r までの連続するすべての区画の雪の量をそれぞれ 1 センチメートルずつ減らします。ただし、操作を行う前の時点で、区画 l, l+1, \ldots, r の中に雪の量が 0 センチメートルの区画が 1 つでもある場合、その組 (l, r) を選ぶことはできません。雪かきは何度でも行うことができ、毎回異なる組 (l, r) を選んでもよく、同じ組を複数回選ぶこともできます。

すべての区画の雪の量をちょうど 0 センチメートルにするために必要な雪かきの最小回数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、区画の個数を表す整数 N が与えられる。
  • 2 行目には、各区画に積もっている雪の量を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

すべての区画の雪の量をちょうど 0 センチメートルにするために必要な雪かきの最小回数を 1 行で出力せよ。

入力例 1

3
3 1 2

出力例 1

4

入力例 2

5
2 3 2 1 4

出力例 2

6

入力例 3

8
5 0 3 0 8 2 0 1

出力例 3

17

Score : 300 pts

Problem Statement

Takahashi is responsible for shoveling snow on the road in front of his house during winter.

The road is divided into N sections, numbered from left to right as section 1, section 2, \ldots, section N. The amount of snow accumulated in section i is A_i centimeters.

Takahashi uses a snow shovel to clear the snow. In one snow shoveling session, he chooses a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N, and reduces the amount of snow in each of the consecutive sections from section l to section r by 1 centimeter. However, if at the time before the operation, any section among sections l, l+1, \ldots, r has 0 centimeters of snow, he cannot choose that pair (l, r). Snow shoveling can be performed any number of times, and he may choose a different pair (l, r) each time, or choose the same pair multiple times.

Find the minimum number of snow shoveling sessions required to make the amount of snow in all sections exactly 0 centimeters.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of sections.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the amount of snow accumulated in each section.

Output

Print in one line the minimum number of snow shoveling sessions required to make the amount of snow in all sections exactly 0 centimeters.

Sample Input 1

3
3 1 2

Sample Output 1

4

Sample Input 2

5
2 3 2 1 4

Sample Output 2

6

Sample Input 3

8
5 0 3 0 8 2 0 1

Sample Output 3

17