Sum of Nodes with Even-Valued Grandparent

You are given a binary tree represented in level order as an array. The tree nodes are given as integers, and a missing node is represented by the string null. Your task is to find the sum of all nodes that have even-valued grandparents.

A node G is considered the grandparent of a node N if there exists some node P such that P is the parent of N and G is the parent of P.

If a node does not have a grandparent or its grandparent's value is odd, it does not contribute to the sum. Use the following recursive relation for processing the tree:

$$\text{sum} = \begin{cases}\;0 & \text{if node is } null\\ \;\text{(if grandparent exists and is even then add node.val)} + \text{recurse on left} + \text{recurse on right} & \text{otherwise}\end{cases}$$

Note: You must construct the binary tree from the given level order input.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains an integer n representing the number of elements in the tree array.
• The second line contains n space-separated values representing the tree nodes in level order. Each value is either an integer or the string null (without quotes). If n = 0, the tree is empty.

outputFormat

Output a single integer to standard output (stdout) representing the sum of all nodes with an even-valued grandparent.

## sample

15
6 7 8 2 7 1 3 9 null 1 4 null null null 5

18

</p>