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?

Problem Note

Input: An array A[] of N integers representing the ratings of each student

Example 1

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.

Example 2

Input: A[] = [1, 5, 2, 1]
Output: 7
Explanation: Candies given = [1, 3, 2, 1]