code: from __future__ import annotations
  
  from abc import abstractmethod
  from collections.abc import Iterable
  from typing import Generic, Protocol, TypeVar
  
  
  
  
  
  
  
  class 					UpperCAmelCase_				(							_a    ):
  
  
  
  
      @abstractmethod
      def __lt__(					self  :   T      ,      lowerCAmelCase  :   T   )	-> bool:
        pass
  
  
  
  
      @abstractmethod
      def __gt__(					self  :   T      ,      lowerCAmelCase  :   T   )	-> bool:
        pass
  
  
  
  
      @abstractmethod
      def __eq__(					self  :   T      ,      lowerCAmelCase  :   object   )	-> bool:
        pass
  
  _SCREAMING_SNAKE_CASE   						=    TypeVar("""T""", bound=Comparable)
  
  
  
  
  
  
  
  class 					UpperCAmelCase_				(							Generic[T]    ):
  
  
  
  
      def __init__(					self  :   List[str]   )	-> None:
        a__     		=     []
        a__     		=     0
  
  
  
  
      def __repr__(					self  :   Tuple   )	-> str:
        return str(self.h   )
  
  
  
  
      def 						__lowerCamelCase (					self  :   Any      ,      lowerCAmelCase  :   int   )	-> int | None:
        if child_idx > 0:
          return (child_idx - 1) // 2
        return None
  
  
  
  
      def 						__lowerCamelCase (					self  :   List[str]      ,      lowerCAmelCase  :   int   )	-> int | None:
        a__     		=     2 * parent_idx + 1
        if left_child_index < self.heap_size:
          return left_child_index
        return None
  
  
  
  
      def 						__lowerCamelCase (					self  :   Tuple      ,      lowerCAmelCase  :   int   )	-> int | None:
        a__     		=     2 * parent_idx + 2
        if right_child_index < self.heap_size:
          return right_child_index
        return None
  
  
  
  
      def 						__lowerCamelCase (					self  :   str      ,      lowerCAmelCase  :   int   )	-> None:
        if index < self.heap_size:
          a__     		=     index
          a__     		=     self.left_child_idx(lowerCAmelCase   )
          a__     		=     self.right_child_idx(lowerCAmelCase   )
          # check which child is larger than its parent
          if left_child is not None and self.h[left_child] > self.h[violation]:
            a__     		=     left_child
          if right_child is not None and self.h[right_child] > self.h[violation]:
            a__     		=     right_child
          # if violation indeed exists
          if violation != index:
            # swap to fix the violation
            a__		,a__     		=     self.h[index], self.h[violation]
            # fix the subsequent violation recursively if any
            self.max_heapify(lowerCAmelCase   )
  
  
  
  
      def 						__lowerCamelCase (					self  :   int      ,      lowerCAmelCase  :   Iterable[T]   )	-> None:
        a__     		=     list(lowerCAmelCase   )
        a__     		=     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(lowerCAmelCase   )
  
  
  
  
      def 						__lowerCamelCase (					self  :   Any   )	-> T:
        if self.heap_size >= 2:
          a__     		=     self.h[0]
          a__     		=     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  :   Dict      ,      lowerCAmelCase  :   T   )	-> None:
        self.h.append(lowerCAmelCase   )
        a__     		=     (self.heap_size - 1) // 2
        self.heap_size += 1
        while idx >= 0:
          self.max_heapify(lowerCAmelCase   )
          a__     		=     (idx - 1) // 2
  
  
  
  
      def 						__lowerCamelCase (					self  :   int   )	-> None:
        a__     		=     self.heap_size
        for j in range(size - 1      ,      0      ,      -1   ):
          a__		,a__     		=     self.h[j], self.h[0]
          self.heap_size -= 1
          self.max_heapify(0   )
        a__     		=     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],
           [103, 9, 1, 7, 11, 15, 25, 201, 209, 107, 5],
           [-45, -2, -5],
       ]:
            print(F"""unsorted array: {unsorted}""")
  
            _SCREAMING_SNAKE_CASE   						=    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(100)
            print(F"""after new value 100 inserted: {heap}""")
  
            heap.heap_sort()
            print(F"""heap-sorted array: {heap}\n""")
  
  
style_context: def 				__lowercase	(						lowerCamelCase__ ,				lowerCamelCase__					)				->Optional[int]:
  
    '''simple docstring'''
  
  
  
  
    sequence.append(lowerCamelCase__					)
  
    a__     		=     0
    while sequence[index] != target:
      index += 1
  
    sequence.pop()
  
    if index == len(lowerCamelCase__					):
      return None
  
    return index
  
  
  if __name__ == "__main__":
       _SCREAMING_SNAKE_CASE   						=    input("""Enter numbers separated by comma:\n""").strip()
       _SCREAMING_SNAKE_CASE   						=    [int(item) for item in user_input.split(""",""")]
  
       _SCREAMING_SNAKE_CASE   						=    input("""Enter a single number to be found in the list:\n""")
       _SCREAMING_SNAKE_CASE   						=    int(target_input)
       _SCREAMING_SNAKE_CASE   						=    sentinel_linear_search(sequence, target)
       if result is not None:
            print(F"""{target} found at positions: {result}""")
       else:
            print("""Not found""")
  
  