






from __future__ import annotations

def    lowerCAmelCase__		(			_a				:	list     ,					_a				:	list			):
		snake_case_ :							str         =				[None] * (len(_a			) + len(_a			))

		snake_case_ :							str         =				0  # pointer to current index for left Half
		snake_case_ :							str         =				0  # pointer to current index for the right Half
		snake_case_ :							Tuple         =				0  # pointer to current index for the sorted array Half

		while pointera < len(_a			) and pointera < len(_a			):
				if left_half[pointera] < right_half[pointera]:
						snake_case_ :							Dict         =				left_half[pointera]
						pointera += 1
						index += 1
				else:
						snake_case_ :							Tuple         =				right_half[pointera]
						pointera += 1
						index += 1
		while pointera < len(_a			):
				snake_case_ :							Union[str, Any]         =				left_half[pointera]
				pointera += 1
				index += 1

		while pointera < len(_a			):
				snake_case_ :							Dict         =				right_half[pointera]
				pointera += 1
				index += 1

		return sorted_array

def    lowerCAmelCase__		(			_a				:	list			):
		if len(_a			) <= 1:
				return array
		# the actual formula to calculate the middle element = left + (right - left) // 2
		# this avoids integer overflow in case of large N
		snake_case_ :							Optional[Any]         =				0 + (len(_a			) - 0) // 2

		# Split the array into halves till the array length becomes equal to One
		# merge the arrays of single length returned by mergeSort function and
		# pass them into the merge arrays function which merges the array
		snake_case_ :							Optional[int]         =				array[:middle]
		snake_case_ :							Union[str, Any]         =				array[middle:]

		return merge(merge_sort(_a			)     ,					merge_sort(_a			)			)


if __name__ == "__main__":
							import doctest

							doctest.testmod()








def    lowerCAmelCase__		(			_a				:	int			):
		if not isinstance(_a     ,					_a			):
				snake_case_ :							Optional[int]         =				F'''Input value of [number={number}] must be an integer'''
				raise TypeError(_a			)
		if number < 1:
				raise ValueError("Input must be a positive integer"			)
		return number * (2 * number - 1)


if __name__ == "__main__":
							import doctest

							doctest.testmod()
