← 返回 citadel 的题目列表Candy
类型：online_judge
Candy
There are n children standing in a line. You are given an integer array ratings, where ratings[i] is the rating of the i-th child.
Give each child at least one candy while satisfying the following conditions:
If ratings[i] > ratings[i - 1], child i must receive more candies than child i - 1.
If ratings[i] > ratings[i + 1], child i must receive more candies than child i + 1.
Return the minimum total number of candies required.
Input Format
First line: an integer n, the number of children.
Second line: n integers representing ratings.
Output Format
Print one integer: the minimum total number of candies required.
Example 1
Input:
3
1 0 2
Output:
5
Explanation: One optimal assignment is [2, 1, 2].
Example 2
Input:
3
1 2 2
Output:
4
Explanation: One optimal assignment is [1, 2, 1].
Constraints
1 <= n <= 100,000
0 <= ratings[i] <= 20,000
Example
Input
3
1 0 2
Output
5