The Timely Delivery Network
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.
Example 1
3 1 5 10
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
4 2 2 8 8
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
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 1 5 10
4 2 2 8 8