Maximum Path Sum in Binary Tree

Find the maximum sum obtainable along any path in a binary tree. A path is a sequence of nodes where consecutive nodes are connected by an edge; it may start and end at any node and need not pass through the root.

Input Format

The first line contains an integer M, the number of level-order tokens. The second line contains M space-separated tokens (integers or null).

Output Format

Print the maximum path sum.