def candies(n, arr):
    count = [None] * len(arr)
    
    # we use Depth-first search
    stack = list(range(len(arr)))
    while len(stack) > 0:
        i = stack[-1]
        # out of array or already known
        if i < 0 or i >= len(arr) or count[i] is not None:
            stack.pop()
        # left unknown value
        elif i >= 1 and arr[i] > arr[i-1] and count[i-1] is None:
            stack.append(i-1)
        # right unknown value
        elif i < len(arr) - 1 and arr[i] > arr[i+1] and count[i+1] is None:
            stack.append(i+1)
        # we know left and right value
        else:
            left = count[i-1] if i >= 1 and arr[i] > arr[i-1] else 0
            right = count[i+1] if i < len(arr) - 1 and arr[i] > arr[i+1] else 0
            count[i] = max(left, right) + 1
            stack.pop()

    return sum(count)