

'''simple docstring'''
def  _lowerCAmelCase      (		_UpperCamelCase		:  Tuple							,				_UpperCamelCase		:  str							,				_UpperCamelCase		:  Optional[Any]							,				_UpperCamelCase		:  Optional[int]       )   ->    str:
     """simple docstring"""




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

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


def  _lowerCAmelCase      (		_UpperCamelCase		:  Tuple       )   ->    Union[str, Any]:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE												=len(_UpperCamelCase       )

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

     return lst


def  _lowerCAmelCase      (		_UpperCamelCase		:  str							,				_UpperCamelCase		:  int       )   ->    Tuple:
     """simple docstring"""




     if not left:
          return right

     if not right:
          return left

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

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


def  _lowerCAmelCase      (		_UpperCamelCase		:  List[str]       )   ->    List[Any]:
     """simple docstring"""




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

     for run in runs:
          sorted_runs.append(insertion_sort(_UpperCamelCase       )       )
     for run in sorted_runs:
          _SCREAMING_SNAKE_CASE												=merge(_UpperCamelCase							,				_UpperCamelCase       )

     return sorted_array


def  _lowerCAmelCase      (		)   ->    Dict:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE												=[5, 9, 10, 3, -4, 5, 1_78, 92, 46, -18, 0, 7]
     _SCREAMING_SNAKE_CASE												=tim_sort(_UpperCamelCase       )
     print(_UpperCamelCase       )


if __name__ == "__main__":
     main()



'''simple docstring'''
def  _lowerCAmelCase      (		_UpperCamelCase		:  list       )   ->    list:
     """simple docstring"""




     for i, _ in enumerate(_UpperCamelCase       ):
          if (i % 2 == 1) == (nums[i - 1] > nums[i]):
               _SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE												=nums[i], nums[i - 1]

     return nums


if __name__ == "__main__":
     print("Enter the array elements:")
     lowerCamelCase				:   Tuple      				=  list(map(int, input().split()))
     print("The unsorted array is:")
     print(array)
     print("Array after Wiggle sort:")
     print(wiggle_sort(array))
