Maximum Building Height

Given a list of building heights in a city, where the heights are represented as integers, your goal is to find the maximum height that can be achieved by adding buildings. You must ensure that the new buildings added do not create any building where the heights are not non-decreasing from left to right or non-increasing from right to left. After that, you need to report the maximum possible height after observing the conditions. Input format: - The first line contains an integer n (1 <= n <= 100000), the number of buildings. - The second line contains n space-separated integers representing the heights of the buildings. Output format: - Print an integer representing the maximum height of a new building that can be added. Example: Input: 5 3 1 4 1 5 Output: 5