

'''simple docstring'''
def       a__    (  _SCREAMING_SNAKE_CASE					:    Optional[Any]							)			-> Union[str, Any]:


	"""simple docstring"""





	UpperCAmelCase_			:	Optional[Any]      =   len(_lowerCamelCase							)

	# Set the gap value to be decreased by a factor of 1.3
	# after each iteration
	UpperCAmelCase_			:	Optional[Any]      =   1.3

	# Continue sorting until the gap is 1
	while gap > 1:
		# Decrease the gap value
		UpperCAmelCase_			:	List[str]      =   int(gap / shrink							)

		# Sort the elements using insertion sort
		for i in range(_lowerCamelCase     ,							len(_lowerCamelCase							)							):
			UpperCAmelCase_			:	Dict      =   collection[i]
			UpperCAmelCase_			:	Optional[Any]      =   i
			while j >= gap and collection[j - gap] > temp:
				UpperCAmelCase_			:	List[Any]      =   collection[j - gap]
				j -= gap
			UpperCAmelCase_			:	List[Any]      =   temp

	return collection


if __name__ == "__main__":
					import doctest

					doctest.testmod()












"""simple docstring"""
class 		a_      :







      '''simple docstring'''

      class 		a_      :







            '''simple docstring'''

            lowerCamelCase__       :				List[Any] =	'_prev', '_data', '_next'




            def __init__(self,     lowerCamelCase_,     lowerCamelCase_,     lowerCamelCase_					):

             '''simple docstring'''



             lowerCamelCase__     :			Optional[int]     				=						link_p
             lowerCamelCase__     :			Optional[Any]     				=						element
             lowerCamelCase__     :			List[Any]     				=						link_n





            def 			a__							(self					):

             '''simple docstring'''



             return (
                 f''' Prev -> {self._prev is not None}, Next -> {self._next is not None}'''
             )




      def __init__(self					):

       '''simple docstring'''



       lowerCamelCase__     :			Any     				=						self._Node(lowerCamelCase_,     lowerCamelCase_,     lowerCamelCase_					)
       lowerCamelCase__     :			Dict     				=						self._Node(lowerCamelCase_,     lowerCamelCase_,     lowerCamelCase_					)
       lowerCamelCase__     :			List[str]     				=						self._trailer
       lowerCamelCase__     :			Union[str, Any]     				=						self._header
       lowerCamelCase__     :			Any     				=						0




      def __len__(self					):

       '''simple docstring'''



       return self._size




      def 			a__							(self					):

       '''simple docstring'''



       return self.__len__() == 0




      def 			a__							(self,     lowerCamelCase_,     lowerCamelCase_,     lowerCamelCase_					):

       '''simple docstring'''



       lowerCamelCase__     :			int     				=						self._Node(lowerCamelCase_,     lowerCamelCase_,     lowerCamelCase_					)
       lowerCamelCase__     :			Optional[int]     				=						new_node
       lowerCamelCase__     :			List[Any]     				=						new_node
       self._size += 1
       return self





      def 			a__							(self,     lowerCamelCase_					):

       '''simple docstring'''



       lowerCamelCase__     :			Optional[Any]     				=						node._prev
       lowerCamelCase__     :			List[str]     				=						node._next

       lowerCamelCase__     :			Tuple     				=						successor
       lowerCamelCase__     :			Tuple     				=						predecessor
       self._size -= 1
       lowerCamelCase__     :			int     				=						node._data
       lowerCamelCase__     :			Dict     				=						None
       del node
       return temp



class 		a_      (	_DoublyLinkedBase ):







      '''simple docstring'''

      def 			a__							(self					):

       '''simple docstring'''



       if self.is_empty():
        raise Exception('List is empty'					)
       return self._header._next._data




      def 			a__							(self					):

       '''simple docstring'''



       if self.is_empty():
        raise Exception('List is empty'					)
       return self._trailer._prev._data




      def 			a__							(self,     lowerCamelCase_					):

       '''simple docstring'''



       return self._insert(self._header,     lowerCamelCase_,     self._header._next					)




      def 			a__							(self,     lowerCamelCase_					):

       '''simple docstring'''



       return self._insert(self._trailer._prev,     lowerCamelCase_,     self._trailer					)




      def 			a__							(self					):

       '''simple docstring'''



       if self.is_empty():
        raise IndexError('remove_first from empty list'					)
       return self._delete(self._header._next					)





      def 			a__							(self					):

       '''simple docstring'''



       if self.is_empty():
        raise IndexError('remove_first from empty list'					)
       return self._delete(self._trailer._prev					)

