数头顶

时间限制: 200 ms 内存限制: 65536 kb
总通过人数: 0 总提交人数: 0

题目描述

n个人站成一排,所有人脸朝着右边。对于第i个人,只有他右边的那些人的身高比他小的时候,他才可以看到那些人的头顶,设他能看到c[i]个人的头顶。

现在Z君给你n个人的身高,请你帮他求出$ \sum_{i=1}^{n}c[i] $的值。

输入

只有一组数据。

第一行为一个整数n 。($1\le n\le80,000$)

第二行为n个数,从左到右第i个数h[i]代表第i个人的身高。($1\le h[i]\le1,000,000,000$)

输出

输出一行,为$ \sum_{i=1}^{n}c[i] $的值。

输入样例

6
10 3 7 4 12 2

输出样例

5

样例解释

从左到右身高为 10 3 7 4 12 2

第一个人能看见第二、三、四个人的头顶;第三个人能看见第四个人的头顶;第五个人能看见最后一个人的头顶。其余的人什么都看不见。

所以答案为3 + 1 + 1 = 5

相关推荐