#E. 牛的高度

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Farmer John 的农场有 $n$ 头牛，给定一个长度为 $n$ 的数组， $h_i$ 为第 $i$ 头牛的高度。

最初它们按照编号 $1-n$ 站成一排，并且第 $i$ 头牛只能看到右边比它矮的牛，当视角看到一头高度大于等于它的牛时 $(j>i,a_j≥a_i)$ ，则无法继续看到这头牛后面的其他牛，即编号 $(j+1,n)$ 。

现在请你算出，每头牛可以看到的牛数量之和。

第一行包含一个整数 $n$ ，表示 Farmer John 的农场有 $n$ 头牛。

第二行 $n$ 个整数 $h_i$ ，表示第 $i$ 头牛的高度。

$1≤n≤3*10^5$ , $1≤h_i≤10^9$ 。

6
10 3 7 4 12 2

按照顺序，每头牛可以看到的数量为

4 + 1 + 2 + 1 + 1 + 0 = 9。