


from copy import deepcopy






class   _lowerCamelCase :




       """simple docstring"""



       def __init__(      self				,       _SCREAMING_SNAKE_CASE = None				,       _SCREAMING_SNAKE_CASE = None		)->None:




         '''simple docstring'''





         if arr is None and size is not None:
           A_      :				Optional[int]		     =					size
           A_      :				List[str]		     =					[0] * size
         elif arr is not None:
           self.init(_SCREAMING_SNAKE_CASE		)
         else:
           raise ValueError('''Either arr or size must be specified'''		)



       def        _snake_case       (      self				,       _SCREAMING_SNAKE_CASE		)->None:




         '''simple docstring'''





         A_      :				Dict		     =					len(_SCREAMING_SNAKE_CASE		)
         A_      :				str		     =					deepcopy(_SCREAMING_SNAKE_CASE		)
         for i in range(1				,       self.size		):
           A_      :				Tuple		     =					self.next_(_SCREAMING_SNAKE_CASE		)
           if j < self.size:
             self.tree[j] += self.tree[i]



       def        _snake_case       (      self		)->list[int]:




         '''simple docstring'''





         A_      :				List[Any]		     =					self.tree[:]
         for i in range(self.size - 1				,       0				,       -1		):
           A_      :				Optional[Any]		     =					self.next_(_SCREAMING_SNAKE_CASE		)
           if j < self.size:
             arr[j] -= arr[i]
         return arr



       @staticmethod
       def        _snake_case       (      _SCREAMING_SNAKE_CASE		)->int:




         '''simple docstring'''





         return index + (index & (-index))



       @staticmethod
       def        _snake_case       (      _SCREAMING_SNAKE_CASE		)->int:




         '''simple docstring'''





         return index - (index & (-index))



       def        _snake_case       (      self				,       _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE		)->None:




         '''simple docstring'''





         if index == 0:
           self.tree[0] += value
           return
         while index < self.size:
           self.tree[index] += value
           A_      :				Any		     =					self.next_(_SCREAMING_SNAKE_CASE		)



       def        _snake_case       (      self				,       _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE		)->None:




         '''simple docstring'''





         self.add(_SCREAMING_SNAKE_CASE				,       value - self.get(_SCREAMING_SNAKE_CASE		)		)



       def        _snake_case       (      self				,       _SCREAMING_SNAKE_CASE		)->int:




         '''simple docstring'''





         if right == 0:
           return 0
         A_      :				Union[str, Any]		     =					self.tree[0]
         right -= 1  # make right inclusive
         while right > 0:
           result += self.tree[right]
           A_      :				Union[str, Any]		     =					self.prev(_SCREAMING_SNAKE_CASE		)
         return result



       def        _snake_case       (      self				,       _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE		)->int:




         '''simple docstring'''





         return self.prefix(_SCREAMING_SNAKE_CASE		) - self.prefix(_SCREAMING_SNAKE_CASE		)



       def        _snake_case       (      self				,       _SCREAMING_SNAKE_CASE		)->int:




         '''simple docstring'''





         return self.query(_SCREAMING_SNAKE_CASE				,       index + 1		)







       def        _snake_case       (      self				,       _SCREAMING_SNAKE_CASE		)->int:




         '''simple docstring'''





         value -= self.tree[0]
         if value < 0:
           return -1

         A_      :				List[Any]		     =					1  # Largest power of 2 <= size
         while j * 2 < self.size:
           j *= 2

         A_      :				Dict		     =					0

         while j > 0:
           if i + j < self.size and self.tree[i + j] <= value:
             value -= self.tree[i + j]
             i += j
           j //= 2
         return i


if __name__ == "__main__":
     import doctest

     doctest.testmod()








def   _SCREAMING_SNAKE_CASE	( SCREAMING_SNAKE_CASE       ):
  if not nums:  # Makes sure that the list is not empty
    raise ValueError('''List is empty'''       )

  A_      :				Optional[int]		     =					sum(SCREAMING_SNAKE_CASE       ) / len(SCREAMING_SNAKE_CASE       )  # Calculate the average
  return sum(abs(x - average       ) for x in nums       ) / len(SCREAMING_SNAKE_CASE       )


if __name__ == "__main__":
     import doctest

     doctest.testmod()




