The Timely Delivery NetworkMedium

The Timely Delivery Network

Medium+30 XP · +10 Aurabinary searchgreedyarrays

UptoSkills Arena is expanding its delivery network! We have N warehouses, located at distinct positions on a straight line. We need to establish a new central distribution hub. This hub will be able to deliver packages to any warehouse in at most T time units. The travel time between two warehouses is the absolute difference of their positions. We want to find the minimum possible value of T such that placing the hub at some location (not necessarily at a warehouse) allows deliveries to all N warehouses within time T. If multiple hub locations achieve this minimum T, choose the one that is farthest to the left.

Input

The first line contains an integer N. The second line contains N space-separated integers, representing the positions of the warehouses.

Output

Print a single integer, the minimum possible delivery time T.

Constraints

1 <= N <= 200000, 0 <= warehouse positions <= 10^9.

Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests

Example 1

Input
3
1 5 10
Output
5

Min pos = 1, Max pos = 10. Difference = 9. Min T = ceil(9/2) = 5. Hub at 5.5. Warehouses at 1, 5, 10. Distances: |5.5-1|=4.5, |5.5-5|=0.5, |5.5-10|=4.5. All <= 5.

Example 2

Input
4
2 2 8 8
Output
3

Min pos = 2, Max pos = 8. Difference = 6. Min T = ceil(6/2) = 3. Hub at 5. Warehouses at 2, 2, 8, 8. Distances: |5-2|=3, |5-8|=3. All <= 3.

Hints