n children stand in a row, each with an integer rating. You hand out candies under two rules: every child gets at least one candy, and any child whose rating is strictly higher than an adjacent neighbor (left or right) must receive strictly more candies than that neighbor.
Return the minimum total number of candies you must hand out.
Input format
Line 1: an integer n, the number of children.
Line 2: n space-separated integers, the ratings in row order (present whenever n >= 1).
Output format
A single integer: the minimum total candies satisfying both rules.
Constraints
- 1 <= n <= 100000
- 0 <= rating[i] <= 1000000000
- Equal adjacent ratings impose no ordering between those two children.