There are N children standing in a line where each child is assigned a rating value. You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
Input: An array A of N integers representing the ratings of each student
Input: A = [1,2,2] Output: 4 Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions.
Input: A = [1, 5, 2, 1] Output: 7 Explanation: Candies given = [1, 3, 2, 1]