Untitled

def giveCandy(ratings):
    n = len(ratings)
    # O(n*log(n))
    sortedRatings = sorted([(ratings[i], i) for i in range(n)])
    candies = [0 for i in range(n)]

    total = 0
    for (rating, i) in sortedRatings:
        candy = 1
        if i>0 and rating > ratings[i-1]:
            candy = max(candy, candies[i-1]+1)
        if i+1<n and rating > ratings[i+1]:
            candy = max(candy, candies[i+1]+1)

        candies[i] = candy
        total += candy

    return total