






def __A					(   __lowerCAmelCase				,	__lowerCAmelCase				,	__lowerCAmelCase				,	__lowerCAmelCase			)->						Optional[int]:





						"""simple docstring"""



						if start == end:
												return start if lst[start] > item else start + 1
						if start > end:
												return start

						_UpperCAmelCase             =    (start + end) // 2
						if lst[mid] < item:
												return binary_search(__lowerCAmelCase				,	__lowerCAmelCase				,	mid + 1				,	__lowerCAmelCase			)
						elif lst[mid] > item:
												return binary_search(__lowerCAmelCase				,	__lowerCAmelCase				,	__lowerCAmelCase				,	mid - 1			)
						else:
												return mid


def __A					(   __lowerCAmelCase			)->						List[Any]:





						"""simple docstring"""



						_UpperCAmelCase             =    len(__lowerCAmelCase			)

						for index in range(1				,	__lowerCAmelCase			):
												_UpperCAmelCase             =    lst[index]
												_UpperCAmelCase             =    binary_search(__lowerCAmelCase				,	__lowerCAmelCase				,	0				,	index - 1			)
												_UpperCAmelCase             =    lst[:pos] + [value] + lst[pos:index] + lst[index + 1 :]

						return lst


def __A					(   __lowerCAmelCase				,	__lowerCAmelCase			)->						List[Any]:





						"""simple docstring"""



						if not left:
												return right

						if not right:
												return left

						if left[0] < right[0]:
												return [left[0], *merge(left[1:]				,	__lowerCAmelCase			)]

						return [right[0], *merge(__lowerCAmelCase				,	right[1:]			)]


def __A					(   __lowerCAmelCase			)->						int:





						"""simple docstring"""



						_UpperCAmelCase             =    len(__lowerCAmelCase			)
						_UpperCAmelCase      ,				_UpperCAmelCase             =    [], []
						_UpperCAmelCase             =    [lst[0]]
						_UpperCAmelCase             =    []
						_UpperCAmelCase             =    1
						while i < length:
												if lst[i] < lst[i - 1]:
																		runs.append(__lowerCAmelCase			)
																		_UpperCAmelCase             =    [lst[i]]
												else:
																		new_run.append(lst[i]			)
												i += 1
						runs.append(__lowerCAmelCase			)

						for run in runs:
												sorted_runs.append(insertion_sort(__lowerCAmelCase			)			)
						for run in sorted_runs:
												_UpperCAmelCase             =    merge(__lowerCAmelCase				,	__lowerCAmelCase			)

						return sorted_array


def __A					(   )->						List[Any]:





						"""simple docstring"""



						_UpperCAmelCase             =    [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
						_UpperCAmelCase             =    tim_sort(__lowerCAmelCase			)
						print(__lowerCAmelCase			)


if __name__ == "__main__":
		main()








from typing import Any





class __lowerCamelCase				:





	"""simple docstring"""






	def __init__(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    []
							_UpperCAmelCase             =    0

	def __str__(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    '<' + str(self.stack					)[1:-1] + '>'
							return printed

	def  UpperCamelCase					(							self ,					UpperCAmelCase					):
							"""simple docstring"""







							self.stack.append(UpperCAmelCase					)
							_UpperCAmelCase             =    self.length + 1

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							self.rotate(1					)
							_UpperCAmelCase             =    self.stack[self.length - 1]
							_UpperCAmelCase             =    self.stack[:-1]
							self.rotate(self.length - 1					)
							_UpperCAmelCase             =    self.length - 1
							return dequeued

	def  UpperCamelCase					(							self ,					UpperCAmelCase					):
							"""simple docstring"""







							for _ in range(UpperCAmelCase					):
													_UpperCAmelCase             =    self.stack[0]
													_UpperCAmelCase             =    self.stack[1:]
													self.put(UpperCAmelCase					)
													_UpperCAmelCase             =    self.length - 1

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    self.get()
							self.put(UpperCAmelCase					)
							self.rotate(self.length - 1					)
							return front

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							return self.length
