n children stand in a line. The array ratings holds the rating of each child. You give candies to the children by these rules:
- Every child gets at least one candy.
- A child with a higher rating than a neighbour gets more candies than that neighbour.
Return the smallest total number of candies you need.
Examples
Example 1:
Input: ratings = [5,3,3,8,9]
Output: 9
Explanation: Give 2, 1, 1, 2, 3 candies. The two children with rating 3 can both get 1, because equal ratings need no difference.
Example 2:
Input: ratings = [1,2,3,4]
Output: 10
Explanation: The ratings go up all the way, so the candies are 1, 2, 3, 4.
Example 3:
Input: ratings = [7,7,7]
Output: 3
Explanation: All ratings are equal, so everyone gets 1 candy.