The n members of a team sit around a round table; ratings[i] is the rating of seat i. Seats i and (i + 1) % n are neighbours, so seat 0 and seat n - 1 are neighbours too (when n >= 2). Each member receives a whole number of tokens under these rules:
- Everyone receives at least 1 token.
- A member whose rating is strictly higher than a neighbour's receives strictly more tokens than that neighbour.
- A member whose rating is equal to a neighbour's receives exactly as many tokens as that neighbour.
Return the smallest possible total number of tokens.
Examples
Input: ratings = [3, 1, 4, 2]
Output: 6
Explanation: tokens [2, 1, 2, 1]. Seat 0 (rating 3) sits next to seat 3
(rating 2) and seat 1 (rating 1), and has more tokens than both.
Input: ratings = [6, 2, 5, 3, 4, 1]
Output: 9
Explanation: tokens [2, 1, 2, 1, 2, 1].
Input: ratings = [1, 4, 4, 2, 3]
Output: 8
Explanation: tokens [1, 2, 2, 1, 2]; the two neighbours rated 4 get the
same number of tokens.
Constraints
1 <= len(ratings) <= 10**50 <= ratings[i] <= 10**9
Goals
- Recognise how a circular arrangement changes a familiar two-pass greedy
- Merge runs of equal values, including a run that wraps around the end of the list
- Find a cut point that turns a cycle of constraints into a straight line