Convert Sorted Array to Balanced Binary Search Tree

You are given a sorted array of n integers in non-decreasing order. Your task is to convert this array into a balanced binary search tree (BST). A balanced BST is defined such that the depth of the two subtrees of every node never differs by more than one.

Each node in the BST should be represented as a JSON object with the following keys:

• value: The integer stored in that node.
• left: The left child subtree (or null if there is no left child).
• right: The right child subtree (or null if there is no right child).

If the input array is empty, output null.

The tree must be built using the strategy of choosing the middle element as the root, recursively applying the same strategy for the left and right partitions.

Note on LaTeX formulas: When describing keys, use the LaTeX representation \(\texttt{value}\), \(\texttt{left}\), and \(\texttt{right}\) for clarity if needed.

inputFormat

The input is read from stdin and consists of two parts:

1. The first line contains an integer n — the number of elements in the sorted array.
2. The second line contains n space‐separated integers in non-decreasing order. If n is 0, the second line may be empty.

outputFormat

Output the balanced BST as a JSON formatted string to stdout. Each node in the BST should be represented as an object with keys \(\texttt{value}\), \(\texttt{left}\), and \(\texttt{right}\). For a missing child, output \(\texttt{null}\) (without quotes).

For example, the BST for the list [1, 2, 3] should be printed as:

{"value":2,"left":{"value":1,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}}

## sample

3
1 2 3

{"value":2,"left":{"value":1,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}}