Find Closest Value in a Balanced Binary Search Tree

You are given a balanced binary search tree (BST) represented in level order form containing n nodes. In this BST, each node contains a distinct integer value. Your task is to find the value of the node which has the minimum absolute difference with a given target value x. If there are multiple nodes with the same minimum difference, output the smallest such node value.

The BST is constructed based on its level order traversal using the following rule: for any node at index i in the array, its left child is at index 2i+1 and its right child is at index 2i+2, if these indices are within bounds. It is guaranteed that the given level order traversal corresponds to a BST.

The mathematical formulation for the absolute difference can be written as:

$$\text{diff} = \lvert node\_value - x \rvert$$

Your goal is to implement a solution that reads the BST and target from standard input and writes the result to standard output.

inputFormat

The input is given via standard input in the following format:

1. An integer n representing the number of nodes in the BST. If n is 0, then the BST is empty.
2. A line with n space-separated integers representing the nodes in level order.
3. An integer x representing the target value.

For example:

7
4 2 6 1 3 5 7
4

outputFormat

Output the value of the node from the BST that has the minimum absolute difference with x. If the BST is empty, output None.

## sample

7
4 2 6 1 3 5 7
4

4

</p>