Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subject to the following requirements:

• Each child must have at least 1 candy.
• Children with a higher rating than their neighbor must get more candies than that neighbor.

Return the minimum number of candies you need to distribute.

Examples

Example 1:

Input: ratings = [1,0,2]

Output: 5

Explanation: You can allocate [2,1,2] candies to the children respectively. The child at index 1 has the lowest rating so gets 1 candy. Both neighbors have higher ratings and get 2 candies each. Total = 2 + 1 + 2 = 5.

Example 2:

Input: ratings = [1,2,2]

Output: 4

Explanation: You can allocate [1,2,1] candies to the children respectively. The child at index 1 has a higher rating than index 0, so gets more candies. The child at index 2 has the same rating as index 1, so the constraint does not apply. Total = 1 + 2 + 1 = 4.

Example 3:

Input: ratings = [1,3,2,2,1]

Output: 7

Explanation: You can allocate [1,2,1,2,1] candies. Total = 1 + 2 + 1 + 2 + 1 = 7.

Constraints

• n == ratings.length
• 1 <= n <= 2 * 10⁴
• 0 <= ratings[i] <= 2 * 10⁴