game
Description
n个小朋友玩游戏,游戏结束之后每个小朋友有一个得分。
小朋友站成一排,你现在要给小朋友发糖。
你需要保证
1.每个小朋友至少有一颗糖
2.如果一个小朋友比他左右两边相邻的小朋友中的某一个分数更高,那么他所被分到的糖也要比他更多一点(至少多一个)
求能够满足条件的最少的话费糖的个数
Input
第一行一个正整数n(1<=n<=100000)
第二行n个正整数表示每个小朋友的得分ai(ai<=100000)
Output
一个正整数,即需要花费的糖的最小个数
Sample 1
Input
Output
Sample 2
Input
Output
Limitation
1s, 64Mb for each test case.
Hint
Free Pascal Code
C Code
C++ Code
Python Code
Java Code
Source
Vijos Original