






from __future__ import annotations

from collections import defaultdict
from dataclasses import dataclass




@dataclass
class        _lowerCAmelCase:





       """simple docstring"""







       a       :	int
       a       :	TreeNode | None								=None
       a       :	TreeNode | None								=None







def 						snake_case      () ->       TreeNode:
  return TreeNode(3			,					TreeNode(9						)			,					TreeNode(2_0			,					TreeNode(1_5						)			,					TreeNode(7						)						)						)

def 						snake_case      (UpperCAmelCase__						) ->       list[int]:

  def depth_first_search(
      UpperCAmelCase__			,					UpperCAmelCase__			,					UpperCAmelCase__						) -> None:
    if not root:
      return

    if depth == len(UpperCAmelCase__						):
      right_view.append(root.val						)

    depth_first_search(root.right			,					depth + 1			,					UpperCAmelCase__						)
    depth_first_search(root.left			,					depth + 1			,					UpperCAmelCase__						)

  UpperCamelCase_:      list					   =       []
  if not root:
    return right_view

  depth_first_search(UpperCAmelCase__			,					0			,					UpperCAmelCase__						)
  return right_view

def 						snake_case      (UpperCAmelCase__						) ->       list[int]:

  def depth_first_search(
      UpperCAmelCase__			,					UpperCAmelCase__			,					UpperCAmelCase__						) -> None:
    if not root:
      return

    if depth == len(UpperCAmelCase__						):
      left_view.append(root.val						)

    depth_first_search(root.left			,					depth + 1			,					UpperCAmelCase__						)
    depth_first_search(root.right			,					depth + 1			,					UpperCAmelCase__						)

  UpperCamelCase_:      list					   =       []
  if not root:
    return left_view

  depth_first_search(UpperCAmelCase__			,					0			,					UpperCAmelCase__						)
  return left_view

def 						snake_case      (UpperCAmelCase__						) ->       list[int]:

  def breadth_first_search(UpperCAmelCase__			,					UpperCAmelCase__						) -> None:
    UpperCamelCase_:      Tuple					   =       [(root, 0)]
    UpperCamelCase_:      List[Any]					   =       defaultdict(UpperCAmelCase__						)

    while queue:
      UpperCamelCase_:      Optional[Any]					   =       queue.pop(0						)
      UpperCamelCase_   ,UpperCamelCase_:      List[str]					   =       first

      lookup[hd].append(node.val						)

      if node.left:
        queue.append((node.left, hd - 1)						)
      if node.right:
        queue.append((node.right, hd + 1)						)

    for pair in sorted(lookup.items()			,					key=lambda UpperCAmelCase__						: each[0]						):
      top_view.append(pair[1][0]						)

  UpperCamelCase_:      list					   =       []
  if not root:
    return top_view

  breadth_first_search(UpperCAmelCase__			,					UpperCAmelCase__						)
  return top_view

def 						snake_case      (UpperCAmelCase__						) ->       list[int]:
  from collections import defaultdict

  def breadth_first_search(UpperCAmelCase__			,					UpperCAmelCase__						) -> None:
    UpperCamelCase_:      Tuple					   =       [(root, 0)]
    UpperCamelCase_:      Any					   =       defaultdict(UpperCAmelCase__						)

    while queue:
      UpperCamelCase_:      List[Any]					   =       queue.pop(0						)
      UpperCamelCase_   ,UpperCamelCase_:      Optional[Any]					   =       first
      lookup[hd].append(node.val						)

      if node.left:
        queue.append((node.left, hd - 1)						)
      if node.right:
        queue.append((node.right, hd + 1)						)

    for pair in sorted(lookup.items()			,					key=lambda UpperCAmelCase__						: each[0]						):
      bottom_view.append(pair[1][-1]						)

  UpperCamelCase_:      list					   =       []
  if not root:
    return bottom_view

  breadth_first_search(UpperCAmelCase__			,					UpperCAmelCase__						)
  return bottom_view


if __name__ == "__main__":
   import doctest

   doctest.testmod()







def 						snake_case      (UpperCAmelCase__ = 4_0_0_0_0_0_0						) ->       int:

  if n <= 1:
    return 0
  UpperCamelCase_:      Dict					   =       0
  UpperCamelCase_:      Union[str, Any]					   =       2
  UpperCamelCase_:      int					   =       0
  while 4 * b + a <= n:
    UpperCamelCase_   ,UpperCamelCase_:      List[str]					   =       b, 4 * b + a
    count += a
  return count + b


if __name__ == "__main__":
   print(F'''{solution() = }''')