Find Floor in a Binary Search Tree

You are given a binary search tree (BST) and a value \( x \). Your task is to find the floor of \( x \) in the BST. The floor of \( x \) is defined as the greatest element in the BST that is less than or equal to \( x \). If there is no such element, return -1.

The BST follows the property that for any node with value \( v \), all nodes in its left subtree have values less than \( v \) and all nodes in its right subtree have values greater than \( v \).

Example:
Consider the BST formed by inserting the nodes in the following order: 8, 4, 12, 2, 6, 1, 14. For \( x = 5 \), the floor is 4 because 4 is the greatest value in the tree that does not exceed 5.

Your solution should read from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input is given in the following format:

n
v1 v2 v3 ... vn
x

where:

• n is an integer representing the number of nodes in the BST.
• v1, v2, ..., vn are the node values inserted into the BST in the given order.
• x is the integer for which you need to find the floor in the BST.

outputFormat

Output a single integer representing the floor of \( x \) in the BST. If no such floor exists, output \(-1\).

## sample

7
8 4 12 2 6 1 14
5

4

</p>