





from __future__ import annotations


def 					__SCREAMING_SNAKE_CASE  (							__lowercase:		list[int]):



  '''simple docstring'''






  __lowerCAmelCase			=				[0] * len(__lowercase)
  for i in range(1     ,							len(__lowercase)):
    __lowerCAmelCase			=				duration_times[i - 1] + waiting_times[i - 1]
  return waiting_times


def 					__SCREAMING_SNAKE_CASE  (							__lowercase:		list[int]     ,							__lowercase:		list[int]):



  '''simple docstring'''






  return [
      duration_time + waiting_times[i]
      for i, duration_time in enumerate(__lowercase)
  ]


def 					__SCREAMING_SNAKE_CASE  (							__lowercase:		list[int]):



  '''simple docstring'''






  return sum(__lowercase) / len(__lowercase)


def 					__SCREAMING_SNAKE_CASE  (							__lowercase:		list[int]):



  '''simple docstring'''






  return sum(__lowercase) / len(__lowercase)


if __name__ == "__main__":
      # process id's
      __lowercase													=			[1, 2, 3]

      # ensure that we actually have processes
      if len(processes) == 0:
            print("""Zero amount of processes""")
            raise SystemExit(0)

      # duration time of all processes
      __lowercase													=			[19, 8, 9]

      # ensure we can match each id to a duration time
      if len(duration_times) != len(processes):
            print("""Unable to match all id's with their duration time""")
            raise SystemExit(0)

      # get the waiting times and the turnaround times
      __lowercase													=			calculate_waiting_times(duration_times)
      __lowercase													=			calculate_turnaround_times(duration_times, waiting_times)

      # get the average times
      __lowercase													=			calculate_average_waiting_time(waiting_times)
      __lowercase													=			calculate_average_turnaround_time(turnaround_times)

      # print all the results
      print("""Process ID\tDuration Time\tWaiting Time\tTurnaround Time""")
      for i, process in enumerate(processes):
            print(
                f"""{process}\t\t{duration_times[i]}\t\t{waiting_times[i]}\t\t"""
                f"""{turnaround_times[i]}"""
            )
      print(f"""Average waiting time = {average_waiting_time}""")
      print(f"""Average turn around time = {average_turnaround_time}""")







class   __snake_case				:






    '''simple docstring'''





    def __init__(   self						:		Any							):

      """simple docstring"""





      __lowerCAmelCase			=				{}
      # indexmap keys are an index and it's values are the number at that index
      __lowerCAmelCase			=				{}





    def 	A		(   self						:		List[Any]			,						snake_case						:		list | str | range			,						snake_case						:		int							):

      """simple docstring"""





      if isinstance(snake_case			,						(range, str)							):
        __lowerCAmelCase			=				list(snake_case							)
      elif not isinstance(snake_case			,						snake_case							):
        raise TypeError(
            '''binary_search_delete() only accepts either a list, range or str'''							)

      __lowerCAmelCase			=				0
      __lowerCAmelCase			=				len(snake_case							) - 1

      while low <= high:
        __lowerCAmelCase			=				(low + high) // 2
        if array[mid] == item:
          array.pop(snake_case							)
          return array
        elif array[mid] < item:
          __lowerCAmelCase			=				mid + 1
        else:
          __lowerCAmelCase			=				mid - 1
      raise ValueError(
          '''Either the item is not in the array or the array was unsorted'''							)





    def 	A		(   self						:		Tuple			,						snake_case						:		list | str | range			,						snake_case						:		int							):

      """simple docstring"""





      if isinstance(snake_case			,						(range, str)							):
        __lowerCAmelCase			=				list(snake_case							)
      elif not isinstance(snake_case			,						snake_case							):
        raise TypeError(
            '''binary_search_insert() only accepts either a list, range or str'''							)

      __lowerCAmelCase			=				0
      __lowerCAmelCase			=				len(snake_case							) - 1

      while low <= high:
        __lowerCAmelCase			=				(low + high) // 2
        if array[mid] == index:
          # If the item already exists in the array,
          # insert it after the existing item
          array.insert(mid + 1			,						snake_case							)
          return array
        elif array[mid] < index:
          __lowerCAmelCase			=				mid + 1
        else:
          __lowerCAmelCase			=				mid - 1

        # If the item doesn't exist in the array, insert it at the appropriate position
      array.insert(snake_case			,						snake_case							)
      return array





    def 	A		(   self						:		Tuple			,						snake_case						:		int			,						snake_case						:		int							):

      """simple docstring"""





      if index in self.indexmap:
        __lowerCAmelCase			=				self.indexmap[index]
        if len(self.numbermap[n]							) == 1:
          del self.numbermap[n]
        else:
          __lowerCAmelCase			=				self.binary_search_delete(self.numbermap[n]			,						snake_case							)

        # Set new index
      __lowerCAmelCase			=				number

      # Number not seen before or empty so insert number value
      if number not in self.numbermap:
        __lowerCAmelCase			=				[index]

      # Here we need to perform a binary search insertion in order to insert
      # The item in the correct place
      else:
        __lowerCAmelCase			=				self.binary_search_insert(
            self.numbermap[number]			,						snake_case							)





    def 	A		(   self						:		List[str]			,						snake_case						:		int							):

      """simple docstring"""





      return self.numbermap.get(snake_case			,						[-1]							)[0]


if __name__ == "__main__":
      import doctest

      doctest.testmod()
