Lowest Common Ancestor in a Binary Search Tree

Given a Binary Search Tree (BST) and two integer values p and q, find the lowest common ancestor (LCA) of the two nodes with these values. In a BST, for any node, all nodes in its left subtree have smaller values and all nodes in its right subtree have greater values. The lowest common ancestor is defined as the deepest node that has both p and q as descendants (where we allow a node to be a descendant of itself).

The algorithm leverages the BST property. If both p and q are less than the current node's value, then the LCA must lie in the left subtree. If both are greater, then it must lie in the right subtree. Otherwise, the current node is the LCA.

The mathematical intuition can be expressed in LaTeX as follows:

Let \(T\) be a BST and let \(v\) be a node in \(T\). Then, \(v\) is the LCA of \(p\) and \(q\) if and only if:

[ (p \leq v \leq q) \quad \text{or} \quad (q \leq v \leq p). ]

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n representing the number of nodes in the BST.
• The second line contains n space-separated integers that represent the insertion order of the nodes into the BST.
• The third line contains two space-separated integers p and q, whose lowest common ancestor must be found in the BST.

outputFormat

Output a single integer to stdout representing the value of the lowest common ancestor of nodes p and q.

## sample

9
6 2 8 0 4 7 9 3 5
2 8

6