


def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	Any:


						'''simple docstring'''






						__snake_case				=		0
						__snake_case				=		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 	_lowerCAmelCase       (    _lowerCAmelCase )						->	Dict:


						'''simple docstring'''






						if len(_lowerCAmelCase ) <= 1:
												return arr, 0
						__snake_case				=		len(_lowerCAmelCase ) // 2
						__snake_case				=		arr[0:mid]
						__snake_case				=		arr[mid:]

						__snake_case		,					__snake_case				=		count_inversions_recursive(_lowerCAmelCase )
						__snake_case		,					__snake_case				=		count_inversions_recursive(_lowerCAmelCase )
						__snake_case		,					__snake_case				=		_count_cross_inversions(_lowerCAmelCase      ,	_lowerCAmelCase )

						__snake_case				=		inversion_p + inversions_q + cross_inversions
						return c, num_inversions





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	Union[str, Any]:


						'''simple docstring'''






						__snake_case				=		[]
						__snake_case				=		__snake_case				=		__snake_case				=		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 	_lowerCAmelCase       (    )						->	int:


						'''simple docstring'''






						__snake_case				=		[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)

						__snake_case				=		count_inversions_bf(_lowerCAmelCase )
						__snake_case		,					__snake_case				=		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()
						__snake_case				=		count_inversions_bf(_lowerCAmelCase )
						__snake_case		,					__snake_case				=		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
						__snake_case				=		[]
						__snake_case				=		count_inversions_bf(_lowerCAmelCase )
						__snake_case		,					__snake_case				=		count_inversions_recursive(_lowerCAmelCase )

						assert num_inversions_bf == num_inversions_recursive == 0
						print("number of inversions = "      ,	_lowerCAmelCase )


if __name__ == "__main__":
	main()









def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	int:


						'''simple docstring'''






						__snake_case				=		abs(_lowerCAmelCase )
						__snake_case				=		0
						while n > 0:
												res += n % 10
												n //= 10
						return res





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	int:


						'''simple docstring'''






						__snake_case				=		abs(_lowerCAmelCase )
						return n if n < 10 else n % 10 + sum_of_digits(n // 10 )





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	int:


						'''simple docstring'''






						return sum(int(_lowerCAmelCase ) for c in str(abs(_lowerCAmelCase ) ) )





def 	_lowerCAmelCase       (    )						->	None:


						'''simple docstring'''






						from collections.abc import Callable
						from timeit import timeit

						def benchmark_a_function(_lowerCAmelCase      ,	_lowerCAmelCase ) -> None:
												__snake_case				=		F'''{func.__name__}({value})'''
												__snake_case				=		timeit(F'''__main__.{call}'''      ,	setup="import __main__" )
												print(F'''{call:56} = {func(_lowerCAmelCase )} -- {timing:.4f} seconds''' )

						for value in (26_2144, 1125_8999_0684_2624, 126_7650_6002_2822_9401_4967_0320_5376):
												for func in (sum_of_digits, sum_of_digits_recursion, sum_of_digits_compact):
																		benchmark_a_function(_lowerCAmelCase      ,	_lowerCAmelCase )
												print()


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	benchmark()





