Gold Stars in a Row

Children stand in a line after a quiz, and scores[i] is the score of child i. The teacher hands out gold stars by two rules:

• every child gets at least one star
• a child with a higher score than a neighbour (the child directly to the left or to the right) gets more stars than that neighbour

Write fewest_stars(scores) that returns the smallest total number of stars the teacher needs.

Examples

fewest_stars([3, 1, 2])         # returns 5
fewest_stars([1, 4, 4, 2])      # returns 6
fewest_stars([5, 4, 3, 2, 1])   # returns 15

In the first example the children get 2, 1 and 2 stars. In the second they get 1, 2, 2 and 1: the two children who both scored 4 have no rule between them, so they do not need the same number of stars.

Constraints

• 0 <= len(scores) <= 100,000
• 0 <= scores[i] <= 10^9

Note

For an empty line the answer is 0.