做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 1405. -- 山峰

1405: 山峰

时间限制: 1 Sec  内存限制: 128 MB
提交: 167  解决: 81
[上一题][提交][讨论版][状态][下一题]

题目描述

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<=109)。

输出

仅一行:快乐值。

样例输入

5
2
1
3
5
9

样例输出

5

提示

说明:s1=0, s2=1, s3=2, s4=1, s5=1。

标签

[上一题][提交][讨论版][状态][下一题]