





from __future__ import annotations







def       UpperCAmelCase							(     _lowerCamelCase      :  Any			,   _lowerCamelCase      :  Any			,   _lowerCamelCase      :  int			,   _lowerCamelCase      :  Union[str, Any]     ):  # noqa: E741





						'''simple docstring'''


						while r - l > 1:
												SCREAMING_SNAKE_CASE__     :				Any   =					(l + r) // 2
												if v[m] >= key:
																		SCREAMING_SNAKE_CASE__     :				Optional[int]   =					m
												else:
																		SCREAMING_SNAKE_CASE__     :				Union[str, Any]   =					m  # noqa: E741
						return r







def       UpperCAmelCase							(     _lowerCamelCase      :  list[int]     ):





						'''simple docstring'''


						if len(_lowerCamelCase     ) == 0:
												return 0

						SCREAMING_SNAKE_CASE__     :				Dict   =					[0] * len(_lowerCamelCase     )
						SCREAMING_SNAKE_CASE__     :				str   =					1

						SCREAMING_SNAKE_CASE__     :				int   =					v[0]

						for i in range(1			,   len(_lowerCamelCase     )     ):
												if v[i] < tail[0]:
																		SCREAMING_SNAKE_CASE__     :				List[Any]   =					v[i]
												elif v[i] > tail[length - 1]:
																		SCREAMING_SNAKE_CASE__     :				Union[str, Any]   =					v[i]
																		length += 1
												else:
																		SCREAMING_SNAKE_CASE__     :				str   =					v[i]

						return length


if __name__ == "__main__":
				import doctest

				doctest.testmod()






from __future__ import annotations







def       UpperCAmelCase							(     _lowerCamelCase      :  list			,   _lowerCamelCase      :  int | None = None			,   _lowerCamelCase      :  int | None = None     ):





						'''simple docstring'''


						if start is None:
												SCREAMING_SNAKE_CASE__     :				Union[str, Any]   =					0

						if end is None:
												SCREAMING_SNAKE_CASE__     :				Any   =					len(_lowerCamelCase     ) - 1

						if start >= end:
												return

						SCREAMING_SNAKE_CASE__     :				List[str]   =					(start + end) // 2

						slowsort(_lowerCamelCase			,   _lowerCamelCase			,   _lowerCamelCase     )
						slowsort(_lowerCamelCase			,   mid + 1			,   _lowerCamelCase     )

						if sequence[end] < sequence[mid]:
												SCREAMING_SNAKE_CASE__,							SCREAMING_SNAKE_CASE__     :				Optional[int]   =					sequence[mid], sequence[end]

						slowsort(_lowerCamelCase			,   _lowerCamelCase			,   end - 1     )


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

				testmod()