Un camino en un árbol binario es una secuencia de nodos distintos en la que cada par de nodos seguidos está unido por una arista; no tiene que pasar por la raíz y tiene al menos un nodo. Su suma es la suma de los valores de sus nodos. Encuentra la mayor suma posible de un camino.

Entrada

El árbol viene en el formato de LeetCode, en dos líneas: la primera tiene un entero \(k\) y la segunda \(k\) elementos separados por espacios, que son el recorrido por niveles del árbol. Cada elemento es el valor de un nodo o null si ese hijo no existe; los hijos de un null no se escriben y los null del final se omiten. Un árbol vacío se escribe con \(k = 0\) y una línea vacía. El árbol tiene entre \(1\) y \(3 \cdot 10^4\) nodos, con valores entre \(-1000\) y \(1000\).

Salida

La mayor suma de un camino.

Ejemplo 1

Entrada

3
1 2 3

Salida

6

Ejemplo 2

Entrada

7
-10 9 20 null null 15 7

Salida

42

Ejemplo 3

Entrada

1
-3

Salida

-3