问题1032--山峰

1032: 山峰

时间限制: 1 Sec  内存限制: 128 MB
提交: 124  解决: 73
[提交] [状态] [讨论版] [命题人:]

题目描述

Rocky山脉有n个山峰,一字排开,从西向东依次编号为1, 2, 3, ……, n。每个山峰的高度可能一样的。编号为i的山峰高度为hi。
罗老师从西往东登山。每到一座山峰,他就回头观望自己走过的艰辛历程。在第i座山峰,他记录下自己回头能看到的山峰数si。
何谓“能看到”?如果在第i座山峰,存在j<k<i,hj<hk,那么第j座山峰就是不可见的。除了不可见的山峰,其余的山峰都是可见的。
回家之后,罗老师把所有的si加起来得到S作为他此次旅行快乐值。现在n座山峰的高度都提供给你了,你能计算出罗老师的快乐值吗?

输入

第一行一个整数n(n<=15000)。
第i+1(1<=i<=n)行是一个整数hi(hi<=10^9)。

输出

仅一行:快乐值。

样例输入 Copy

5
2
1
3
5
9

样例输出 Copy

5

提示

【样例说明】
说明:s1=0, s2=1, s3=2, s4=1, s5=1。

来源/分类