Largest Smaller Value in BST

Given a binary search tree (BST) constructed from a sorted array of numbers, and a query value \(x\), your task is to find the largest value in the BST that is smaller than or equal to \(x\). If no such value exists, return -1.

You must first build a balanced BST from the given sorted array. Then, using an iterative search method, determine the correct value. The BST property ensures that for any node, values in the left subtree are smaller and those in the right subtree are larger.

inputFormat

The input consists of three lines:
1. The first line contains an integer \(N\), representing the number of nodes in the BST.
2. The second line contains \(N\) space-separated integers in increasing order, which form the sorted array used to construct the BST.
3. The third line contains a number \(x\) (which can be an integer or a floating-point value) that is the query value.

outputFormat

Output a single line containing the largest value in the BST that is smaller than or equal to \(x\). If no such value exists, output -1.

5
1 2 3 4 5
3

3