Maximum Path Sum in a Binary Tree

You are given a binary tree, represented in level order as a JSON array where the integer values represent node values and the string null represents an absent child. Your task is to compute the maximum path sum in the tree.

A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not necessarily need to go through the root.

The maximum path sum is defined as the largest possible sum of any path. Mathematically, if you denote a path as a sequence of nodes with values \(a_1, a_2, \dots, a_k\), then the sum is \(S = a_1 + a_2 + \dots + a_k\), and you need to maximize \(S\).

Note: The input is given via standard input and the output should be printed to standard output.

inputFormat

The input is a single line containing a JSON array that represents the level order traversal of a binary tree. Each element in the array is either an integer or the literal null, which indicates a missing node.

For example:

[1,2,3]

represents the binary tree:

    1
   / \
  2   3

outputFormat

Output a single integer which is the maximum path sum in the given binary tree.

## sample

[1,2,3]

6