E - View of the Mountain Range Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は山岳地帯をハイキングしています。この地帯には N 個の山が一列に並んでおり、左から i 番目の山の標高は H_i です。

高橋君は各山の山頂に立ち、左方向（インデックスが小さい方向）を眺めます。そして、ある条件を満たす山がいくつ見えるかを数えることを楽しみにしています。

山 i の山頂から左方向を見たとき、山 j（j < i）が 見える とは、以下の条件をともに満たすことをいいます。

  1. H_j > H_i である。すなわち、山 j は山 i より厳密に高い。特に、H_j = H_i の場合は見えるとはみなしません。
  2. j < k < i を満たす全ての整数 k について H_k < H_j が成り立つ。すなわち、山 j と山 i の間にある全ての山の標高が H_j より厳密に低い。

条件2は、山 j と山 i の間に山 j 以上の標高をもつ山がある場合、山 j は遮られて見えなくなることを意味しています。j = i - 1 の場合（山 j と山 i が隣接している場合）は間に山が存在しないため、条件2は自動的に満たされます。

なお、この問題における「見える」の定義は上記の通りであり、現実の視線遮蔽の物理的なモデルとは異なります。

山 i の山頂から左方向に見える山の数を C_i とします。山 1 からは左方向に山が存在しないため C_1 = 0 です。

i = 1, 2, \ldots, N の全てについて C_i の合計値、すなわち \displaystyle\sum_{i=1}^{N} C_i を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq H_i \leq 10^9
  • 入力は全て整数である。
  • 同じ標高の山が複数存在することもある。

入力

N
H_1 H_2 \ldots H_N
  • 1 行目には、山の個数を表す整数 N が与えられる。
  • 2 行目には、各山の標高を表す N 個の整数 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。

出力

\displaystyle\sum_{i=1}^{N} C_i の値を 1 行で出力せよ。

入力例 1

5
3 1 4 1 5

出力例 1

2

入力例 2

5
2 3 1 2 1

出力例 2

4

入力例 3

10
5 3 8 6 7 2 9 1 4 3

出力例 3

9

入力例 4

20
10 4 15 7 12 3 18 6 14 2 20 8 16 5 11 1 19 9 13 17

出力例 4

25

入力例 5

1
1000000000

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi is hiking in a mountainous region. In this region, N mountains are lined up in a row, and the elevation of the i-th mountain from the left is H_i.

Takahashi stands at the summit of each mountain and looks to the left (in the direction of decreasing index). He enjoys counting how many mountains satisfying certain conditions are visible.

When looking to the left from the summit of mountain i, mountain j (j < i) is visible if and only if both of the following conditions are satisfied:

  1. H_j > H_i. That is, mountain j is strictly higher than mountain i. In particular, if H_j = H_i, mountain j is not considered visible.
  2. For all integers k satisfying j < k < i, H_k < H_j holds. That is, all mountains between mountain j and mountain i have elevations strictly lower than H_j.

Condition 2 means that if there is a mountain between mountain j and mountain i with elevation greater than or equal to H_j, then mountain j is blocked and not visible. When j = i - 1 (i.e., mountain j and mountain i are adjacent), there are no mountains between them, so condition 2 is automatically satisfied.

Note that the definition of "visible" in this problem is as described above and differs from a physical model of real line-of-sight occlusion.

Let C_i be the number of mountains visible to the left from the summit of mountain i. Since there are no mountains to the left of mountain 1, C_1 = 0.

Find the total of C_i for all i = 1, 2, \ldots, N, that is, \displaystyle\sum_{i=1}^{N} C_i.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq H_i \leq 10^9
  • All inputs are integers.
  • There may be multiple mountains with the same elevation.

Input

N
H_1 H_2 \ldots H_N
  • The first line contains an integer N representing the number of mountains.
  • The second line contains N integers H_1, H_2, \ldots, H_N separated by spaces, representing the elevation of each mountain.

Output

Output the value of \displaystyle\sum_{i=1}^{N} C_i on a single line.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

2

Sample Input 2

5
2 3 1 2 1

Sample Output 2

4

Sample Input 3

10
5 3 8 6 7 2 9 1 4 3

Sample Output 3

9

Sample Input 4

20
10 4 15 7 12 3 18 6 14 2 20 8 16 5 11 1 19 9 13 17

Sample Output 4

25

Sample Input 5

1
1000000000

Sample Output 5

0