<p>There are <code>n</code> children standing in a line. Each child is assigned a rating value given in the integer array <code>ratings</code>.</p>

<p>You are giving candies to these children subjected to the following requirements:</p>

<ul>
	<li>Each child must have at least one candy.</li>
	<li>Children with a higher rating get more candies than their neighbors.</li>
</ul>

<p>Return <em>the minimum number of candies you need to have to distribute the candies to the children</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> ratings = [1,0,2]
<strong>Output:</strong> 5
<strong>Explanation:</strong> You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> ratings = [1,2,2]
<strong>Output:</strong> 4
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == ratings.length</code></li>
	<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= ratings[i] &lt;= 2 * 10<sup>4</sup></code></li>
</ul>

'''
    len(ratings) == n

    each child needs at least one candy
    children with higher ratings than their neighbors need more candy than that neighbor
        if children have the same ratings, they can have equal candy
    

    1 0 2

        X
    X   X


    2 1 2 3 1 2
    
    1 0 2 4 0 3
          X
          X   X
        X X   X
    X   X X   X

    0 0 1 2 0 1
    1 0 0 1 0 0


          X
    X   X X   X
    X X X X X X
    2 1 2 3 1 2


'''

class Solution:
    def candy(self, ratings: List[int]) -> int:
        forward = [0] * len(ratings)
        backward = [0] * len(ratings)
        
        b = len(ratings) - 2
        for f in range(1, len(ratings)):

            if ratings[f] > ratings[f - 1]:
                forward[f] = forward[f - 1] + 1

            if ratings[b] > ratings[b + 1]:
                backward[b] = backward[b + 1] + 1
                
            b -= 1

        print(forward)
        print(backward)

        totalCandy = len(ratings)
        for i in range(len(ratings)):
            totalCandy += max(forward[i], backward[i])
        
        return totalCandy

19500