





def   a_   (			lowerCAmelCase_				:      Tuple     ):
   __lowerCAmelCase							     =     0
   __lowerCAmelCase							     =     len(lowerCAmelCase_     )

   for i in range(n - 1     ):
      for j in range(i + 1,     lowerCAmelCase_     ):
         if arr[i] > arr[j]:
            num_inversions += 1

   return num_inversions

def   a_   (			lowerCAmelCase_				:      Union[str, Any]     ):
   if len(lowerCAmelCase_     ) <= 1:
      return arr, 0
   __lowerCAmelCase							     =     len(lowerCAmelCase_     ) // 2
   __lowerCAmelCase							     =     arr[0:mid]
   __lowerCAmelCase							     =     arr[mid:]

   __lowerCAmelCase     ,     __lowerCAmelCase							     =     count_inversions_recursive(lowerCAmelCase_     )
   __lowerCAmelCase     ,     __lowerCAmelCase							     =     count_inversions_recursive(lowerCAmelCase_     )
   __lowerCAmelCase     ,     __lowerCAmelCase							     =     _count_cross_inversions(lowerCAmelCase_,     lowerCAmelCase_     )

   __lowerCAmelCase							     =     inversion_p + inversions_q + cross_inversions
   return c, num_inversions

def   a_   (			lowerCAmelCase_				:      Optional[Any],     lowerCAmelCase_				:      Optional[Any]     ):
   __lowerCAmelCase							     =     []
   __lowerCAmelCase							     =     __lowerCAmelCase							     =     __lowerCAmelCase							     =     0
   while i < len(lowerCAmelCase_     ) and j < len(lowerCAmelCase_     ):
      if p[i] > q[j]:
         # if P[1] > Q[j], then P[k] > Q[k] for all  i < k <= len(P)
         # These are all inversions. The claim emerges from the
         # property that P is sorted.
         num_inversion += len(lowerCAmelCase_     ) - i
         r.append(q[j]     )
         j += 1
      else:
         r.append(p[i]     )
         i += 1

   if i < len(lowerCAmelCase_     ):
      r.extend(p[i:]     )
   else:
      r.extend(q[j:]     )

   return r, num_inversion

def   a_   (			):
   __lowerCAmelCase							     =     [10, 2, 1, 5, 5, 2, 11]

   # this arr has 8 inversions:
   # (10, 2), (10, 1), (10, 5), (10, 5), (10, 2), (2, 1), (5, 2), (5, 2)

   __lowerCAmelCase							     =     count_inversions_bf(lowerCAmelCase_     )
   __lowerCAmelCase     ,     __lowerCAmelCase							     =     count_inversions_recursive(lowerCAmelCase_     )

   assert num_inversions_bf == num_inversions_recursive == 8

   print('number of inversions = ',     lowerCAmelCase_     )

   # testing an array with zero inversion (a sorted arr_1)

   arr_a.sort()
   __lowerCAmelCase							     =     count_inversions_bf(lowerCAmelCase_     )
   __lowerCAmelCase     ,     __lowerCAmelCase							     =     count_inversions_recursive(lowerCAmelCase_     )

   assert num_inversions_bf == num_inversions_recursive == 0
   print('number of inversions = ',     lowerCAmelCase_     )

   # an empty list should also have zero inversions
   __lowerCAmelCase							     =     []
   __lowerCAmelCase							     =     count_inversions_bf(lowerCAmelCase_     )
   __lowerCAmelCase     ,     __lowerCAmelCase							     =     count_inversions_recursive(lowerCAmelCase_     )

   assert num_inversions_bf == num_inversions_recursive == 0
   print('number of inversions = ',     lowerCAmelCase_     )


if __name__ == "__main__":
     main()








from collections.abc import Sequence

def   a_   (			lowerCAmelCase_				:      Sequence[float],     lowerCAmelCase_				:      bool = False     ):
   if not arr:
      return 0

   __lowerCAmelCase							     =     0 if allow_empty_subarrays else float('-inf'     )
   __lowerCAmelCase							     =     0.0
   for num in arr:
      __lowerCAmelCase							     =     max(0 if allow_empty_subarrays else num,     curr_sum + num     )
      __lowerCAmelCase							     =     max(lowerCAmelCase_,     lowerCAmelCase_     )

   return max_sum


if __name__ == "__main__":
     from doctest import testmod

     testmod()

     _snake_case  :   Optional[Any]						   =  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
     print(F"""{max_subarray_sum(nums) = }""")

