
from __future__ import annotations

from abc import abstractmethod
from collections.abc import Iterable
from typing import Generic, Protocol, TypeVar



class     a  (     _A    ):

     '''simple docstring'''





     @abstractmethod
     def __lt__(			self     :    T      ,					__snake_case     :    T       ):
         pass
     @abstractmethod
     def __gt__(			self     :    T      ,					__snake_case     :    T       ):
         pass




     @abstractmethod
     def __eq__(			self     :    T      ,					__snake_case     :    object       ):
         pass


_lowerCamelCase    				=		TypeVar('T', bound=Comparable)



class     a  (     Generic[T]    ):

     '''simple docstring'''





     def __init__(			self     :    Optional[Any]       ):
         UpperCAmelCase_											=  []
         UpperCAmelCase_											=  0
     def __repr__(			self     :    Optional[Any]       ):
         return str(self.h       )
     def 						lowerCamelCase_     (			self     :    List[str]      ,					__snake_case     :    int       ):
         if child_idx > 0:
             return (child_idx - 1) // 2
         return None
     def 						lowerCamelCase_     (			self     :    Optional[Any]      ,					__snake_case     :    int       ):
         UpperCAmelCase_											=  2 * parent_idx + 1
         if left_child_index < self.heap_size:
             return left_child_index
         return None
     def 						lowerCamelCase_     (			self     :    str      ,					__snake_case     :    int       ):
         UpperCAmelCase_											=  2 * parent_idx + 2
         if right_child_index < self.heap_size:
             return right_child_index
         return None
     def 						lowerCamelCase_     (			self     :    Dict      ,					__snake_case     :    int       ):
         if index < self.heap_size:
             UpperCAmelCase_											=  index
             UpperCAmelCase_											=  self.left_child_idx(__snake_case       )
             UpperCAmelCase_											=  self.right_child_idx(__snake_case       )
             # check which child is larger than its parent
             if left_child is not None and self.h[left_child] > self.h[violation]:
                 UpperCAmelCase_											=  left_child
             if right_child is not None and self.h[right_child] > self.h[violation]:
                 UpperCAmelCase_											=  right_child
             # if violation indeed exists
             if violation != index:
                 # swap to fix the violation
                 UpperCAmelCase_				,							UpperCAmelCase_											=  self.h[index], self.h[violation]
                 # fix the subsequent violation recursively if any
                 self.max_heapify(__snake_case       )
     def 						lowerCamelCase_     (			self     :    Optional[int]      ,					__snake_case     :    Iterable[T]       ):
         UpperCAmelCase_											=  list(__snake_case       )
         UpperCAmelCase_											=  len(self.h       )
         if self.heap_size > 1:
             # max_heapify from right to left but exclude leaves (last level)
             for i in range(self.heap_size // 2 - 1      ,					-1      ,					-1       ):
                 self.max_heapify(__snake_case       )
     def 						lowerCamelCase_     (			self     :    List[str]       ):
         if self.heap_size >= 2:
             UpperCAmelCase_											=  self.h[0]
             UpperCAmelCase_											=  self.h.pop(-1       )
             self.heap_size -= 1
             self.max_heapify(0       )
             return me
         elif self.heap_size == 1:
             self.heap_size -= 1
             return self.h.pop(-1       )
         else:
             raise Exception('''Empty heap'''       )
     def 						lowerCamelCase_     (			self     :    Tuple      ,					__snake_case     :    T       ):
         self.h.append(__snake_case       )
         UpperCAmelCase_											=  (self.heap_size - 1) // 2
         self.heap_size += 1
         while idx >= 0:
             self.max_heapify(__snake_case       )
             UpperCAmelCase_											=  (idx - 1) // 2




     def 						lowerCamelCase_     (			self     :    Tuple       ):
         UpperCAmelCase_											=  self.heap_size
         for j in range(size - 1      ,					0      ,					-1       ):
             UpperCAmelCase_				,							UpperCAmelCase_											=  self.h[j], self.h[0]
             self.heap_size -= 1
             self.max_heapify(0       )
         UpperCAmelCase_											=  size


if __name__ == "__main__":
 import doctest

 # run doc test
 doctest.testmod()

 # demo
 for unsorted in [
     [0],
     [2],
     [3, 5],
     [5, 3],
     [5, 5],
     [0, 0, 0, 0],
     [1, 1, 1, 1],
     [2, 2, 3, 5],
     [0, 2, 2, 3, 5],
     [2, 5, 3, 0, 2, 3, 0, 3],
     [6, 1, 2, 7, 9, 3, 4, 5, 10, 8],
     [1_03, 9, 1, 7, 11, 15, 25, 2_01, 2_09, 1_07, 5],
     [-45, -2, -5],
 ]:
  print(F"unsorted array: {unsorted}")

  _lowerCamelCase    				=		Heap()
  heap.build_max_heap(unsorted)
  print(F"after build heap: {heap}")

  print(F"max value: {heap.extract_max()}")
  print(F"after max value removed: {heap}")

  heap.insert(1_00)
  print(F"after new value 100 inserted: {heap}")

  heap.heap_sort()
  print(F"heap-sorted array: {heap}\n")











import decimal




def       SCREAMING_SNAKE_CASE			( )						->							int:
    UpperCAmelCase_											=  0
    UpperCAmelCase_											=  decimal.Context(prec=105   )
    for i in range(2 ,  100   ):
        UpperCAmelCase_											=  decimal.Decimal(__UpperCamelCase   )
        UpperCAmelCase_											=  number.sqrt(__UpperCamelCase   )
        if len(str(__UpperCamelCase   )   ) > 1:
            answer += int(str(__UpperCamelCase   )[0]   )
            UpperCAmelCase_											=  str(__UpperCamelCase   )[2:101]
            answer += sum(int(__UpperCamelCase   ) for x in sqrt_number_str   )
    return answer


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 print(F"{solution() = }")





