
"""simple docstring"""


class 	__a	:






       def __init__(	self			:				str							,   UpperCAmelCase_			:				Tuple							,   UpperCAmelCase_			:				str      )->	Optional[Any]:







              """simple docstring"""
              UpperCamelCase       			=		name
              UpperCamelCase       			=		val






       def __str__(	self			:				Tuple      )->	List[Any]:







              """simple docstring"""
              return f"{self.__class__.__name__}({self.name}, {self.val})"






       def __lt__(	self			:				List[Any]							,   UpperCAmelCase_			:				Any      )->	Optional[int]:







              """simple docstring"""
              return self.val < other.val





class 	__a	:






       def __init__(	self			:				Tuple							,   UpperCAmelCase_			:				str      )->	Tuple:







              """simple docstring"""
              UpperCamelCase       			=		{}
              UpperCamelCase       			=		{}
              UpperCamelCase       			=		self.build_heap(UpperCAmelCase_      )






       def __getitem__(	self			:				Tuple							,   UpperCAmelCase_			:				Union[str, Any]      )->	str:







              """simple docstring"""
              return self.get_value(UpperCAmelCase_      )






       def 						_SCREAMING_SNAKE_CASE							(	self			:				int							,   UpperCAmelCase_			:				Union[str, Any]      )->	Union[str, Any]:







              """simple docstring"""
              return (idx - 1) // 2






       def 						_SCREAMING_SNAKE_CASE							(	self			:				Tuple							,   UpperCAmelCase_			:				str      )->	Union[str, Any]:







              """simple docstring"""
              return idx * 2 + 1






       def 						_SCREAMING_SNAKE_CASE							(	self			:				int							,   UpperCAmelCase_			:				int      )->	List[Any]:







              """simple docstring"""
              return idx * 2 + 2






       def 						_SCREAMING_SNAKE_CASE							(	self			:				List[str]							,   UpperCAmelCase_			:				Any      )->	Optional[int]:







              """simple docstring"""
              return self.heap_dict[key]






       def 						_SCREAMING_SNAKE_CASE							(	self			:				List[Any]							,   UpperCAmelCase_			:				Any      )->	int:







              """simple docstring"""
              UpperCamelCase       			=		len(UpperCAmelCase_      ) - 1
              UpperCamelCase       			=		self.get_parent_idx(UpperCAmelCase_      )

              for idx, i in enumerate(UpperCAmelCase_      ):
                     UpperCamelCase       			=		idx
                     UpperCamelCase       			=		i.val

              for i in range(UpperCAmelCase_							,   -1							,   -1      ):
                     self.sift_down(UpperCAmelCase_							,   UpperCAmelCase_      )
              return array






       def 						_SCREAMING_SNAKE_CASE							(	self			:				Optional[Any]							,   UpperCAmelCase_			:				Union[str, Any]							,   UpperCAmelCase_			:				Any      )->	Dict:







              """simple docstring"""
              while True:
                     UpperCamelCase       			=		self.get_left_child_idx(UpperCAmelCase_      )  # noqa: E741
                     UpperCamelCase       			=		self.get_right_child_idx(UpperCAmelCase_      )

                     UpperCamelCase       			=		idx
                     if l < len(UpperCAmelCase_      ) and array[l] < array[idx]:
                            UpperCamelCase       			=		l
                     if r < len(UpperCAmelCase_      ) and array[r] < array[smallest]:
                            UpperCamelCase       			=		r

                     if smallest != idx:
                            UpperCamelCase			,							UpperCamelCase       			=		array[smallest], array[idx]
                            (
                                (
                                UpperCamelCase
                            )			,							(
                                UpperCamelCase
                            )			,							
                            )       			=		(
                                self.idx_of_element[array[smallest]],
                                self.idx_of_element[array[idx]],
                            )
                            UpperCamelCase       			=		smallest
                     else:
                            break






       def 						_SCREAMING_SNAKE_CASE							(	self			:				Optional[Any]							,   UpperCAmelCase_			:				Any      )->	Union[str, Any]:







              """simple docstring"""
              UpperCamelCase       			=		self.get_parent_idx(UpperCAmelCase_      )
              while p >= 0 and self.heap[p] > self.heap[idx]:
                     UpperCamelCase			,							UpperCamelCase       			=		self.heap[idx], self.heap[p]
                     UpperCamelCase			,							UpperCamelCase       			=		(
                         self.idx_of_element[self.heap[idx]],
                         self.idx_of_element[self.heap[p]],
                     )
                     UpperCamelCase       			=		p
                     UpperCamelCase       			=		self.get_parent_idx(UpperCAmelCase_      )






       def 						_SCREAMING_SNAKE_CASE							(	self			:				Optional[Any]      )->	int:







              """simple docstring"""
              return self.heap[0]






       def 						_SCREAMING_SNAKE_CASE							(	self			:				List[Any]      )->	str:







              """simple docstring"""
              UpperCamelCase			,							UpperCamelCase       			=		self.heap[-1], self.heap[0]
              UpperCamelCase			,							UpperCamelCase       			=		(
                  self.idx_of_element[self.heap[-1]],
                  self.idx_of_element[self.heap[0]],
              )

              UpperCamelCase       			=		self.heap.pop()
              del self.idx_of_element[x]
              self.sift_down(0							,   self.heap      )
              return x






       def 						_SCREAMING_SNAKE_CASE							(	self			:				Optional[int]							,   UpperCAmelCase_			:				List[Any]      )->	Tuple:







              """simple docstring"""
              self.heap.append(UpperCAmelCase_      )
              UpperCamelCase       			=		len(self.heap      ) - 1
              UpperCamelCase       			=		node.val
              self.sift_up(len(self.heap      ) - 1      )






       def 						_SCREAMING_SNAKE_CASE							(	self			:				Dict      )->	str:







              """simple docstring"""
              return len(self.heap      ) == 0






       def 						_SCREAMING_SNAKE_CASE							(	self			:				int							,   UpperCAmelCase_			:				List[str]							,   UpperCAmelCase_			:				int      )->	Tuple:







              """simple docstring"""
              assert (
                  self.heap[self.idx_of_element[node]].val > new_value
              ), "newValue must be less that current value"
              UpperCamelCase       			=		new_value
              UpperCamelCase       			=		new_value
              self.sift_up(self.idx_of_element[node]      )





SCREAMING_SNAKE_CASE			  =  Node("""R""", -1)
SCREAMING_SNAKE_CASE			  =  Node("""B""", 6)
SCREAMING_SNAKE_CASE			  =  Node("""A""", 3)
SCREAMING_SNAKE_CASE			  =  Node("""X""", 1)
SCREAMING_SNAKE_CASE			  =  Node("""E""", 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
SCREAMING_SNAKE_CASE			  =  MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print("""Min Heap - before decrease key""")
for i in my_min_heap.heap:
      print(i)

print("""Min Heap - After decrease key of node [B -> -17]""")
my_min_heap.decrease_key(b, -17)

# After
for i in my_min_heap.heap:
      print(i)

if __name__ == "__main__":
      import doctest

      doctest.testmod()







"""simple docstring"""


SCREAMING_SNAKE_CASE			  =  {}



def 						lowerCamelCase__      (				UpperCAmelCase_		,   UpperCAmelCase_		,   UpperCAmelCase_					)->				int:







       """simple docstring"""

       # if we are absent twice, or late 3 consecutive days,
       # no further prize strings are possible
       if late == 3 or absent == 2:
              return 0

       # if we have no days left, and have not failed any other rules,
       # we have a prize string
       if days == 0:
              return 1

       # No easy solution, so now we need to do the recursive calculation

       # First, check if the combination is already in the cache, and
       # if yes, return the stored value from there since we already
       # know the number of possible prize strings from this point on
       UpperCamelCase       			=		(days, absent, late)
       if key in cache:
              return cache[key]

       # now we calculate the three possible ways that can unfold from
       # this point on, depending on our attendance today

       # 1) if we are late (but not absent), the "absent" counter stays as
       # it is, but the "late" counter increases by one
       UpperCamelCase       			=		_calculate(days - 1		,   UpperCAmelCase_		,   late + 1					)

       # 2) if we are absent, the "absent" counter increases by 1, and the
       # "late" counter resets to 0
       UpperCamelCase       			=		_calculate(days - 1		,   absent + 1		,   0					)

       # 3) if we are on time, this resets the "late" counter and keeps the
       # absent counter
       UpperCamelCase       			=		_calculate(days - 1		,   UpperCAmelCase_		,   0					)

       UpperCamelCase       			=		state_late + state_absent + state_ontime

       UpperCamelCase       			=		prizestrings
       return prizestrings



def 						lowerCamelCase__      (				UpperCAmelCase_ = 30					)->				int:







       """simple docstring"""
       return _calculate(UpperCAmelCase_		,   absent=0		,   late=0					)


if __name__ == "__main__":
      print(solution())





