Candy

Children stand in a line; ratings[i] is child i's rating. Hand out candies so that:

• every child gets at least one candy, and
• a child with a higher rating than a neighbour gets more candies than that neighbour.

Return the minimum total number of candies.

Example 1

Input: ratings = [1,0,2]
Output: 5

Give 2, 1, 2.

Example 2

Input: ratings = [1,2,2]
Output: 4

Give 1, 2, 1. Equal neighbours have no rule between them.

Example 3

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

Give 1, 2, 1, 2, 1.

Constraints

• 1 <= ratings.length <= 2 * 10^5
• 0 <= ratings[i] <= 10^5