Lowest Common Ancestor in a Binary Tree

You are given a binary tree represented in level order (BFS) where the value -1 indicates a missing node. Given two integers \(n_1\) and \(n_2\), your task is to find the Lowest Common Ancestor (LCA) of the two nodes.

The Lowest Common Ancestor of two nodes \(n_1\) and \(n_2\) is defined as the deepest node that has both \(n_1\) and \(n_2\) as descendants (where we allow a node to be a descendant of itself). Formally, if we denote \(LCA(n_1, n_2)\) as the required node, then it satisfies: \[ \text{LCA}(n_1, n_2) = \text{the deepest node } v \text{ such that } n_1 \text{ and } n_2 \text{ are in the subtree rooted at } v. \]

If either \(n_1\) or \(n_2\) is not present in the tree, output -1.

The tree is provided as a list of space-separated integers in level order, where -1 indicates a null child.

inputFormat

The input is taken from stdin and consists of two lines:

• The first line contains space-separated integers representing the nodes of the binary tree in level order; -1 represents a missing node.
• The second line contains two space-separated integers \(n_1\) and \(n_2\).

outputFormat

Output a single integer to stdout representing the lowest common ancestor of \(n_1\) and \(n_2\). If either node does not exist in the tree, output -1.

## sample

3 5 1 6 2 0 8 -1 -1 7 4
5 1

3

</p>