E - Ball Transfer Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

N 人の人が左右一列に並んでおり、左から i 番目 (1 \leq i \leq N) の人の身長は H_i です。身長が同じ人が複数いることもあります。

N 人の各人はボールを 1 つずつ持っており、それぞれ右方向に投げます。i 番目の人が投げたボールは、i 番目の人より右側にいて、かつ i 番目の人よりも厳密に身長が高い人のうち、最も左にいる人がキャッチします。すなわち、j > i かつ H_j > H_i を満たす j のうち最小の j に対応する人がキャッチします。そのような人が一人もいなければ、そのボールは誰にもキャッチされません。

i 番目の人が投げたボールを j 番目の人がキャッチしたとき（i < j）、その転送のコストを、i 番目の人から j 番目の人までの間にいる全員（i 番目の人と j 番目の人自身を含む）の身長の最小値、すなわち \min(H_i, H_{i+1}, \ldots, H_j) と定義します。誰にもキャッチされなかったボールのコストは 0 とします。

N 人それぞれが投げたボールの転送コストの合計値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq H_i \leq 10^9
  • 入力はすべて整数である

入力

N
H_1 H_2 \ldots H_N
  • 1 行目には、人数を表す整数 N が与えられる。
  • 2 行目には、左から i 番目 (i = 1, 2, \ldots, N) の人の身長を表す整数 H_i が、スペース区切りで N 個与えられる。

出力

N 人それぞれが投げたボールの転送コストの合計値を 1 行で出力せよ。

入力例 1

5
3 1 4 1 5

出力例 1

4

入力例 2

4
5 5 5 5

出力例 2

0

入力例 3

8
2 7 3 5 1 6 4 8

出力例 3

16

入力例 4

15
10 3 7 2 8 1 5 12 4 6 9 3 11 2 15

出力例 4

37

入力例 5

1
1000000000

出力例 5

0

Score : 466 pts

Problem Statement

N people are standing in a single row from left to right, and the height of the i-th person from the left (1 \leq i \leq N) is H_i. Multiple people may have the same height.

Each of the N people holds one ball and throws it to the right. The ball thrown by the i-th person is caught by the leftmost person among those who are to the right of the i-th person and are strictly taller than the i-th person. That is, the ball is caught by the person corresponding to the smallest j satisfying j > i and H_j > H_i. If no such person exists, the ball is not caught by anyone.

When the j-th person catches the ball thrown by the i-th person (i < j), the cost of this transfer is defined as the minimum height among all people between the i-th and j-th person (including the i-th and j-th person themselves), that is, \min(H_i, H_{i+1}, \ldots, H_j). The cost of a ball that is not caught by anyone is 0.

Find the total sum of the transfer costs of the balls thrown by each of the N people.

Constraints

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

Input

N
H_1 H_2 \ldots H_N
  • The first line contains an integer N representing the number of people.
  • The second line contains N integers H_i separated by spaces, representing the height of the i-th person from the left (i = 1, 2, \ldots, N).

Output

Output in one line the total sum of the transfer costs of the balls thrown by each of the N people.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

4

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Sample Input 3

8
2 7 3 5 1 6 4 8

Sample Output 3

16

Sample Input 4

15
10 3 7 2 8 1 5 12 4 6 9 3 11 2 15

Sample Output 4

37

Sample Input 5

1
1000000000

Sample Output 5

0