






'''simple docstring'''




import logging
import os
import threading
import time


try:
    import warnings
except ImportError:
    lowerCamelCase_												=					None

try:
    import msvcrt
except ImportError:
    lowerCamelCase_												=					None

try:
    import fcntl
except ImportError:
    lowerCamelCase_												=					None


# Backward compatibility
# ------------------------------------------------
try:
    TimeoutError
except NameError:
    lowerCamelCase_												=					OSError


# Data
# ------------------------------------------------
lowerCamelCase_												=					[
    '''Timeout''',
    '''BaseFileLock''',
    '''WindowsFileLock''',
    '''UnixFileLock''',
    '''SoftFileLock''',
    '''FileLock''',
]

lowerCamelCase_												=					'''3.0.12'''


lowerCamelCase_												=					None

def 					__lowercase						(			)       ->						Optional[int]:

      '''simple docstring'''


      global _logger
      _A			     =	_logger or logging.getLogger(__name__       )
      return _logger

class    _UpperCAmelCase			(     snake_case_						):




   """simple docstring"""

   def __init__(		self :	Union[str, Any]      ,      __UpperCAmelCase :	Dict		):





         '''simple docstring'''





         _A			     =	lock_file
         return None

   def __str__(		self :	Tuple		):





         '''simple docstring'''





         _A			     =	f'''The file lock \'{self.lock_file}\' could not be acquired.'''
         return temp





class    _UpperCAmelCase			:




   """simple docstring"""

   def __init__(		self :	List[Any]      ,      __UpperCAmelCase :	Any		):





         '''simple docstring'''





         _A			     =	lock
         return None

   def __enter__(		self :	Union[str, Any]		):





         '''simple docstring'''





         return self.lock

   def __exit__(		self :	Tuple      ,      __UpperCAmelCase :	Any      ,      __UpperCAmelCase :	Dict      ,      __UpperCAmelCase :	Union[str, Any]		):





         '''simple docstring'''





         self.lock.release()
         return None





class    _UpperCAmelCase			:




   """simple docstring"""

   def __init__(		self :	Union[str, Any]      ,      __UpperCAmelCase :	Tuple      ,      __UpperCAmelCase :	Optional[int]=-1      ,      __UpperCAmelCase :	Any=None		):





         '''simple docstring'''





         _A			     =	max_filename_length if max_filename_length is not None else 255
         # Hash the filename if it's too long
         _A			     =	self.hash_filename_if_too_long(__UpperCAmelCase      ,      __UpperCAmelCase		)
         # The path to the lock file.
         _A			     =	lock_file

         # The file descriptor for the *_lock_file* as it is returned by the
         # os.open() function.
         # This file lock is only NOT None, if the object currently holds the
         # lock.
         _A			     =	None

         # The default timeout value.
         _A			     =	timeout

         # We use this lock primarily for the lock counter.
         _A			     =	threading.Lock()

         # The lock counter is used for implementing the nested locking
         # mechanism. Whenever the lock is acquired, the counter is increased and
         # the lock is only released, when this value is 0 again.
         _A			     =	0
         return None

   @property
   def 						lowerCAmelCase (		self :	str		):





         '''simple docstring'''





         return self._lock_file

   @property
   def 						lowerCAmelCase (		self :	Union[str, Any]		):





         '''simple docstring'''





         return self._timeout

   @timeout.setter
   def 						lowerCAmelCase (		self :	Optional[int]      ,      __UpperCAmelCase :	Tuple		):





         '''simple docstring'''





         _A			     =	float(__UpperCAmelCase		)
         return None

   def 						lowerCAmelCase (		self :	List[str]		):





         '''simple docstring'''





         raise NotImplementedError()

   def 						lowerCAmelCase (		self :	Dict		):





         '''simple docstring'''





         raise NotImplementedError()

   @property
   def 						lowerCAmelCase (		self :	Union[str, Any]		):





         '''simple docstring'''





         return self._lock_file_fd is not None

   def 						lowerCAmelCase (		self :	List[Any]      ,      __UpperCAmelCase :	Union[str, Any]=None      ,      __UpperCAmelCase :	Tuple=0.05		):





         '''simple docstring'''





         if timeout is None:
               _A			     =	self.timeout

         # Increment the number right at the beginning.
         # We can still undo it, if something fails.
         with self._thread_lock:
               self._lock_counter += 1

         _A			     =	id(self		)
         _A			     =	self._lock_file
         _A			     =	time.time()
         try:
               while True:
                     with self._thread_lock:
                           if not self.is_locked:
                                 logger().debug(f'''Attempting to acquire lock {lock_id} on {lock_filename}'''		)
                                 self._acquire()

                     if self.is_locked:
                           logger().debug(f'''Lock {lock_id} acquired on {lock_filename}'''		)
                           break
                     elif timeout >= 0 and time.time() - start_time > timeout:
                           logger().debug(f'''Timeout on acquiring lock {lock_id} on {lock_filename}'''		)
                           raise Timeout(self._lock_file		)
                     else:
                           logger().debug(
                               f'''Lock {lock_id} not acquired on {lock_filename}, waiting {poll_intervall} seconds ...'''		)
                           time.sleep(__UpperCAmelCase		)
         except:  # noqa
               # Something did go wrong, so decrement the counter.
               with self._thread_lock:
                     _A			     =	max(0      ,      self._lock_counter - 1		)

               raise
         return _Acquire_ReturnProxy(lock=self		)

   def 						lowerCAmelCase (		self :	Union[str, Any]      ,      __UpperCAmelCase :	Dict=False		):





         '''simple docstring'''





         with self._thread_lock:
               if self.is_locked:
                     self._lock_counter -= 1

                     if self._lock_counter == 0 or force:
                           _A			     =	id(self		)
                           _A			     =	self._lock_file

                           logger().debug(f'''Attempting to release lock {lock_id} on {lock_filename}'''		)
                           self._release()
                           _A			     =	0
                           logger().debug(f'''Lock {lock_id} released on {lock_filename}'''		)

         return None

   def __enter__(		self :	Optional[Any]		):





         '''simple docstring'''





         self.acquire()
         return self

   def __exit__(		self :	Any      ,      __UpperCAmelCase :	Optional[int]      ,      __UpperCAmelCase :	int      ,      __UpperCAmelCase :	Optional[Any]		):





         '''simple docstring'''





         self.release()
         return None

   def __del__(		self :	int		):





         '''simple docstring'''





         self.release(force=__UpperCAmelCase		)
         return None

   def 						lowerCAmelCase (		self :	Optional[Any]      ,      __UpperCAmelCase :	str      ,      __UpperCAmelCase :	int		):





         '''simple docstring'''





         _A			     =	os.path.basename(__UpperCAmelCase		)
         if len(__UpperCAmelCase		) > max_length and max_length > 0:
               _A			     =	os.path.dirname(__UpperCAmelCase		)
               _A			     =	str(hash(__UpperCAmelCase		)		)
               _A			     =	filename[: max_length - len(__UpperCAmelCase		) - 8] + "..." + hashed_filename + ".lock"
               return os.path.join(__UpperCAmelCase      ,      __UpperCAmelCase		)
         else:
               return path





class    _UpperCAmelCase			(     snake_case_						):




   """simple docstring"""

   def __init__(		self :	Optional[int]      ,      __UpperCAmelCase :	int      ,      __UpperCAmelCase :	List[Any]=-1      ,      __UpperCAmelCase :	Dict=None		):





         '''simple docstring'''





         from .file_utils import relative_to_absolute_path

         super().__init__(__UpperCAmelCase      ,      timeout=__UpperCAmelCase      ,      max_filename_length=__UpperCAmelCase		)
         _A			     =	"\\\\?\\" + relative_to_absolute_path(self.lock_file		)

   def 						lowerCAmelCase (		self :	Any		):





         '''simple docstring'''





         _A			     =	os.O_RDWR | os.O_CREAT | os.O_TRUNC

         try:
               _A			     =	os.open(self._lock_file      ,      __UpperCAmelCase		)
         except OSError:
               pass
         else:
               try:
                     msvcrt.locking(__UpperCAmelCase      ,      msvcrt.LK_NBLCK      ,      1		)
               except OSError:
                     os.close(__UpperCAmelCase		)
               else:
                     _A			     =	fd
         return None

   def 						lowerCAmelCase (		self :	List[str]		):





         '''simple docstring'''





         _A			     =	self._lock_file_fd
         _A			     =	None
         msvcrt.locking(__UpperCAmelCase      ,      msvcrt.LK_UNLCK      ,      1		)
         os.close(__UpperCAmelCase		)

         try:
               os.remove(self._lock_file		)
         # Probably another instance of the application
         # that acquired the file lock.
         except OSError:
               pass
         return None





class    _UpperCAmelCase			(     snake_case_						):




   """simple docstring"""

   def __init__(		self :	Optional[int]      ,      __UpperCAmelCase :	int      ,      __UpperCAmelCase :	Any=-1      ,      __UpperCAmelCase :	List[str]=None		):





         '''simple docstring'''





         _A			     =	os.statvfs(os.path.dirname(__UpperCAmelCase		)		).f_namemax
         super().__init__(__UpperCAmelCase      ,      timeout=__UpperCAmelCase      ,      max_filename_length=__UpperCAmelCase		)

   def 						lowerCAmelCase (		self :	List[Any]		):





         '''simple docstring'''





         _A			     =	os.O_RDWR | os.O_CREAT | os.O_TRUNC
         _A			     =	os.open(self._lock_file      ,      __UpperCAmelCase		)

         try:
               fcntl.flock(__UpperCAmelCase      ,      fcntl.LOCK_EX | fcntl.LOCK_NB		)
         except OSError:
               os.close(__UpperCAmelCase		)
         else:
               _A			     =	fd
         return None

   def 						lowerCAmelCase (		self :	Dict		):





         '''simple docstring'''





         _A			     =	self._lock_file_fd
         _A			     =	None
         fcntl.flock(__UpperCAmelCase      ,      fcntl.LOCK_UN		)
         os.close(__UpperCAmelCase		)
         return None





class    _UpperCAmelCase			(     snake_case_						):




   """simple docstring"""

   def 						lowerCAmelCase (		self :	Optional[Any]		):





         '''simple docstring'''





         _A			     =	os.O_WRONLY | os.O_CREAT | os.O_EXCL | os.O_TRUNC
         try:
               _A			     =	os.open(self._lock_file      ,      __UpperCAmelCase		)
         except OSError:
               pass
         else:
               _A			     =	fd
         return None

   def 						lowerCAmelCase (		self :	Dict		):





         '''simple docstring'''





         os.close(self._lock_file_fd		)
         _A			     =	None

         try:
               os.remove(self._lock_file		)
         # The file is already deleted and that's what we want.
         except OSError:
               pass
         return None





lowerCamelCase_												=					None

if msvcrt:
    lowerCamelCase_												=					WindowsFileLock
elif fcntl:
    lowerCamelCase_												=					UnixFileLock
else:
    lowerCamelCase_												=					SoftFileLock

    if warnings is not None:
        warnings.warn('''only soft file lock is available''')







"""simple docstring"""




from __future__ import annotations


def   __magic_name__	(      __snake_case				:       list[int]  ) ->				list[int]:
       if len(__snake_case  ) == 0:
              return array

       lowercase		,    lowercase    :				Tuple       		=							min(__snake_case  ), max(__snake_case  )

       # Compute the variables
       lowercase    :				Optional[Any]       		=							_max - _min + 1
       lowercase		,    lowercase    :				List[str]       		=							[0] * holes_range, [0] * holes_range

       # Make the sorting.
       for i in array:
              lowercase    :				Tuple       		=							i - _min
              lowercase    :				str       		=							i
              holes_repeat[index] += 1

       # Makes the array back by replacing the numbers.
       lowercase    :				Union[str, Any]       		=							0
       for i in range(__snake_case  ):
              while holes_repeat[i] > 0:
                     lowercase    :				Tuple       		=							holes[i]
                     index += 1
                     holes_repeat[i] -= 1

    # Returns the sorted array.
       return array


if __name__ == "__main__":
   import doctest

   doctest.testmod()
   _A			:       str   		=       input("""Enter numbers separated by comma:\n""")
   _A			:       Optional[Any]   		=       [int(x) for x in user_input.split(""",""")]
   print(pigeon_sort(unsorted))


