Candy Distribution Problem

You are given a line of children, each with a rating. Every child can only observe the two adjacent children (one to the left and one to the right). A child is concerned only with an adjacent child if that child has a lower rating. In other words, if two adjacent children have equal ratings, no candy comparison is required between them.

For fairness, if two adjacent children have different ratings, the child with the higher rating must receive more candies than the child with the lower rating. Additionally, to encourage every child, each child must receive at least $1$ candy. Note that a child only checks the neighbors with lower ratings to decide if they have fewer candies.

Given these rules, determine the minimum number of candies needed to distribute to all the children.

Input Explanation: The first line contains an integer $n$, the number of children. The second line contains $n$ space-separated integers representing the ratings of the children.

Output Explanation: Output a single integer, the minimum total number of candies required.

Constraints:

• $1 \leq n \leq 10^5$
• $0 \leq rating \leq 10^5$

inputFormat

The input consists of two lines:

1. The first line contains an integer $n$, the number of children.
2. The second line contains $n$ integers, which represent the ratings of the children separated by spaces.

outputFormat

Output a single integer representing the minimum number of candies needed to distribute, such that all conditions are met.

sample

3
1 2 2

4