You are given a sequence of n integers a1, a2, ..., an. Determine a real number x such…
- User
You are given a sequence of n integers a1, a2, ..., an.
Determine a real number x such that the weakness of the sequence a1 - x, a2 - x, ..., an - x is as small as possible.
The weakness of a sequence is defined as the maximum value of the poorness over all segments (contiguous subsequences) of a sequence.
The poorness of a segment is defined as the absolute value of sum of the elements of segment. Input
The first line contains one integer n (1 ≤ n ≤ 200 000), the length of a sequence.
The second line contains n integers a1, a2, ..., an (|ai| ≤ 10 000).
Output
Output a real number denoting the minimum possible weakness of a1 - x, a2 - x, ..., an - x. Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.
Examples
Input
3 1 2 3
Output
1.000000000000000
Input
4 1 2 3 4
Output
2.000000000000000
Input
10 1 10 2 9 3 8 4 7 5 6
Output
4.500000000000000
Note
For the first case, the optimal value of x is 2 so the sequence becomes - 1, 0, 1 and the max poorness occurs at the segment "-1" or segment "1". The poorness value (answer) equals to 1 in this case.
For the second sample the optimal value of x is 2.5 so the sequence becomes - 1.5, - 0.5, 0.5, 1.5 and the max poorness occurs on segment "-1.5 -0.5" or "0.5 1.5". The poorness value (answer) equals to 2 in this case.
Assistant
We need to minimize over x the weakness of sequence b_i = a_i - x. Weakness = max over all contiguous segments of |sum(b_i on segment)|. We need to find min_{x} max_{segment} |sum_{i in segment} (a_i - x)|.
Let's denote for a fixed x, define the transformed sequence b_i = a_i - x. Then the maximum absolute subarray sum (max subarray sum in absolute value) is the weakness. Note that it's the maximum of two things: the maximum subarray sum (positive) and the absolute value of the minimum subarray sum (negative), but since we take absolute value, it's max( max_{segment} S(segment), - min_{segment} S(segment) ), where S = sum(b_i). Actually for any segment, |S| = max(S, -S). So weakness = max( max_{segment} S, - min_{segment} S ). So it's the maximum of the maximum subarray sum and the negative of the minimum subarray sum. (Both computed on b).
Thus weakness(x) = max( max_subarray_sum(b), - min_subarray_sum(b) ).
Let’s define f(x) = max_subarray_sum of b, g(x) = - min_subarray_sum of b. Then weakness(x) = max(f(x), g(x)).
Now b_i = a_i - x. So sum over segment = sum_{i in seg} a_i - x * length(seg). So S_seg(x) = A - x * L, where A = sum a_i over seg, L = length.
Thus f(x) = max_{seg} (A - xL). Since for any segment, we can compute A - xL. But max over seg of linear functions in x: each segment gives a line h_seg(x) = A - L x. Then f(x) = max_{seg} h_seg(x). Similarly, - min_subarray_sum(b) = - min_{seg} (A - x L) = max_{seg} ( - (A - xL) )? Actually - min_{seg} S = - min_{seg} (A - xL) = max_{seg} ( - (A - xL) )? Wait, min_{seg} (A - xL) is a minimum of linear functions. So - min_{seg} (A - xL) is the negative of a minimum, which equals max_{seg} ( - (A - xL) )? Not exactly: - min_i f_i(x) = max_i ( - f_i(x) ). So if we let segments index i, then g(x) = - min_{seg} (A - xL) = max_{seg} ( -A + xL ). So g(x) = max_{seg} ( xL - A ). So g(x) is also a maximum of linear functions (with slopes = L (positive integer from 1 to n) and intercept = -A). So both f(x) and g(x) are convex piecewise linear functions? Actually f(x) = max of decreasing lines (slope -L ≤ 0). So f is convex? Max of linear functions is convex regardless of slopes. Since we are taking max of lines, it's convex. The lines have negative slopes, so f is decreasing? Not necessarily monotone because max of decreasing lines: each line is decreasing, so for larger x, each line decreases, so the maximum also decreases? Actually if all lines are decreasing, then for any x1 < x2, each line value at x2 ≤ at x1, so the max at x2 ≤ max at x1. So f(x) is non-increasing. Similarly, g(x) = max of increasing lines (slope L ≥ 0), so g(x) is non-decreasing. So weakness(x) = max( f(x), g(x) ) where f decreasing, g increasing. So the minimum of max(f,g) occurs at the point where f(x) = g(x) (or crossing region). Because as x increases, f decreases, g increases, so the maximum of the two is a V-shaped function (convex? actually it's like the upper envelope of a decreasing convex function and an increasing convex function; it's convex? Let's check: h(x)=max(f(x),g(x)). f convex decreasing, g convex increasing. The max of two convex functions is convex. Yes, convex. So we can ternary search? But careful: the domain for x is real numbers. f and g are piecewise linear convex. So h(x) is convex piecewise linear. So we can find the minimum via ternary search (since convex unimodal) or more efficiently by binary search on derivative? But we need high precision.
However n up to 200k, so we can compute f(x) and g(x) for any given x in O(n) using Kadane's algorithm (max subarray sum, and min subarray sum). So we can do ternary search on x to minimize h(x). Since h is convex, ternary search works. But need to set search range.
What is the range of x? x can be any real. Since a_i bounded [-10000,10000]. For x far negative, b_i = a_i - x large positive, then max subarray sum will be huge, min subarray sum maybe also large positive? Actually b_i large positive => all b_i large positive. Then max subarray sum = sum of all (positive) => roughly n*(something). min subarray sum will be positive too (since all positive), so - min = negative? Actually if all positive, min subarray sum is the smallest positive value, which is the smallest element? Actually for all positive, the min subarray sum is the minimum single element? Because any subarray sum is positive and larger than each element? Actually if all positive, the minimum subarray sum is the minimum element (since any larger segment adds more positives). So min subarray sum >0, then g(x) = -min_subarray_sum < 0? Wait g(x) = - min_subarray_sum(b). But if min_subarray_sum is positive, then g(x) is negative. But weakness is defined as max(f, g). But g being negative would be less than f positive, so weakness = f. So for x far negative, f is large positive, so h is large. For x far positive, b_i negative large in magnitude, then max subarray sum might be negative? Actually if all negative, max subarray sum is the maximum subarray sum, which would be the least negative (maybe the max element). But it could be negative. However weakness uses absolute values: we take max(f, g). f = max_subarray_sum, which could be negative, but then g = - min_subarray_sum would be positive (since min_subarray_sum is negative, -min is positive). The weakness should be nonnegative anyway. Actually if all b_i are negative, then max subarray sum is the maximum (still negative, maybe close to zero), but the absolute poorness of a segment is |sum|; the segment with largest absolute sum could be the one with most negative sum (largest magnitude). So indeed g(x) = - min_subarray_sum (where min is the most negative) gives the positive magnitude. So weakness = max( max_subarray_sum, - min_subarray_sum ) but note that max_subarray_sum could be negative, but then it's less than - min_subarray_sum? Possibly. But more precisely, weakness = max over segments |sum| = max( max_subarray_sum, - min_subarray_sum ) but only if we consider that max_subarray_sum is the maximum of sums (could be negative) and -min_subarray_sum is the maximum of absolute values of negative sums? Actually if max_subarray_sum is negative, then its absolute value is -max_subarray_sum? Wait careful: max_subarray_sum = maximum over segments of S. If S is always negative, then the maximum is the least negative, which has smallest absolute value. The maximum absolute value among negatives is from the most negative sum, which is min_subarray_sum, and its absolute is -min_subarray_sum. So the overall maximum absolute sum is indeed max( max_subarray_sum, - min_subarray_sum )? But if max_subarray_sum is negative, it's less than - min_subarray_sum (since - min_subarray_sum is positive, max_subarray_sum is negative), so max(f, g) = g. If max_subarray_sum is positive, then it might be larger than g. So the formula holds for any sign. So weakness = max(f,g) as defined.
Thus for x far positive, b_i negative large, f(x) might be negative (or possibly zero if zero?), but g(x) = -min_subarray_sum will be large positive because min_subarray_sum is very negative (large magnitude). So h(x) is large. So h(x) goes to infinity as |x| → ∞, because one of f or g becomes large. So there is a finite minimum.
We can bound x to some interval. For x = average of all a_i? Not necessarily. Since subtracting x is shifting the sequence. The weakness is the maximum absolute deviation from zero of subarray sums after shift. This looks like we are trying to center the sequence to minimize the maximum absolute subarray sum. That is reminiscent of Chebyshev center? Possibly the optimal x is median of something? But we can ternary search.
We need to find x such that f(x) and g(x) cross. Because f decreasing, g increasing, so h(x) = max(f,g) minimal at crossing point where f ≈ g. So we can find x that makes f(x) and g(x) as close as possible.
But careful: f and g are piecewise linear convex functions; their crossing might be an interval if they coincide over a range? Possibly when the slopes differ, there is a unique point. But we can find the minimum of h exactly via ternary search on x.
Precision requirement: relative or absolute error 1e-6. So we can run ternary search for maybe 100 iterations to get high precision.
But need to set search bounds. Since a_i ∈ [-10000,10000] and n ≤ 200k, the maximum possible sum magnitude is n10000 = 2e9, and x could be within a similar range. Actually if we set x = 0, b_i = a_i, weakness ≤ n10000? Actually max absolute subarray sum can be up to n10000 = 2e9. So the weakness values are up to 2e9. The optimal x likely lies within [min(a_i), max(a_i)]? Not exactly: consider a_i all equal to c, then b_i = c - x. For any segment, sum = L(c-x). Then weakness = max_{L} |L*(c-x)| = n*|c-x|? Actually the maximum over L from 1 to n, but absolute value increases with L? |L*(c-x)| increases with L, so max is n*|c-x|. So weakness = n*|c-x|, minimized at x=c, gives 0. So optimal x = average? Actually all equal, any x = c gives 0. So x can be exactly c. So x is in the range of values.
But if a_i vary, optimal x might be something like median of prefix sums? There is known problem: minimize maximum absolute subarray sum after subtracting constant: this is equivalent to finding x such that the maximum deviation of cumulative sums from a line is minimized? Let's think: define prefix sums P_k = sum_{i=1}^k b_i = sum_{i=1}^k (a_i - x) = Q_k - k x, where Q_k = sum_{i=1}^k a_i. Then the subarray sum from l+1 to r = P_r - P_l. So absolute subarray sum = |P_r - P_l|. Then weakness = max_{0 ≤ l < r ≤ n} |P_r - P_l| = max_{0≤l<r≤n} |(Q_r - r x) - (Q_l - l x)| = max_{0≤l<r≤n} |(Q_r - Q_l) - x (r - l)|. This is similar to the maximum distance between two points on the path of cumulative sums with transformation. Another viewpoint: For given x, define points (i, Q_i - i x) for i=0..n (with Q_0=0). Then the weakness is the maximum vertical distance between any two points (max - min of these points). Indeed, max_{l<r} |P_r - P_l| = max_i P_i - min_i P_i (since the max absolute difference between any two points equals the range of the sequence). Actually for any sequence, the maximum absolute difference between two elements is equal to (max - min) if we consider both signs? Wait: Given a set of values, the maximum absolute difference between any two is indeed max - min, because the absolute difference between the max and min is the largest difference; any other pair difference is ≤ max - min. And since max - min is nonnegative, it's equal to max_{l,r} |value_r - value_l|. So weakness(x) = (max_{i} P_i) - (min_{i} P_i). Because P_0=0. Check: For i=0..n, let M = max P_i, m = min P_i. Then M - m is the maximum absolute difference. Indeed, if we take l at min index and r at max index (or vice versa), we get absolute difference M - m. So weakness(x) = range of P_i.
Thus we have P_i = Q_i - i x. So weakness(x) = max_i (Q_i - i x) - min_i (Q_i - i x). That's a classic expression: we want to choose x to minimize the range of these affine functions in i. The points (i, Q_i) with x as a slope we subtract? Actually consider lines L_i(x) = Q_i - i x. For each i, L_i(x) is a linear function of x. Then weakness(x) = max_i L_i(x) - min_i L_i(x). This is the difference between the maximum of a family of lines and the minimum. So we need to minimize this difference over x.
That's a known problem that can be solved by ternary search, or by computing the convex hull and finding the x that equalizes the upper envelope and lower envelope? Indeed, we want to find x that minimizes the vertical span between the upper envelope (U(x) = max_i L_i(x)) and lower envelope (L(x) = min_i L_i(x)). Since U(x) is convex (max of lines with slopes -i? Actually each line L_i(x) = Q_i - i x is linear with slope -i (negative for i>0) and intercept Q_i. So U(x) = max_i (Q_i - i x) is convex? Max of linear functions is convex. Actually slopes are negative, so as x increases, each line decreases; the max of decreasing lines is decreasing, but still convex. L(x) = min_i (Q_i - i x) is concave? Min of linear functions is concave. Actually min of linear functions is concave. But the range U-L is convex? Let's check: U is convex, -L is convex? L concave => -L convex. So U + (-L) = U - L is sum of two convex functions? Not exactly: U - L = U + (-L). Since both are convex, their sum is convex. Yes, convex + convex = convex. So h(x) = U(x) - L(x) is convex. So ternary search works.
Thus we can compute for a given x: compute P_i = Q_i - i x for i=0..n, find max and min, difference = weakness. That's O(n). Q_i prefix sums of a.
Now we need to find minimum of h(x) = max_i P_i - min_i P_i. Since n up to 200k, we can ternary search on x in appropriate range. Let's determine bounds for x.
We need to guarantee that the optimal x lies within some interval [L, R] such that h(x) is convex and minimal inside. Since a_i bounded, we can derive bounds.
Observe that for x very large positive, say x > max a_i + something, then b_i = a_i - x are negative; P_i = sum of negatives is decreasing? Actually Q_i - i x: As x → +∞, each term -i x dominates, so P_i ~ -i x, so max_i P_i will be the one with smallest i (maybe i=0 gives 0? Actually i=0: P_0 = 0 - 0x = 0. For i>0, P_i negative large). So max = 0 (from i=0). min_i P_i will be the most negative, which for large x is approximately -n x. So h(x) ≈ 0 - (-n x) = n x, which grows linearly. Similarly for x → -∞, a_i - x are large positive, P_i ~ -i x (since x negative, -i x positive large), also i=0 gives 0, but max_i P_i becomes large positive (like -n x for x negative? Actually if x → -∞, -i x = i|x| large positive, so max_i P_i is for i=n: Q_n - n x, with Q_n bounded, so ~ -n x → +∞; min_i P_i is 0 (i=0). So h(x) ≈ (-n x) - 0 = -n x = n|x|, also large. So h(x) grows to infinity in both directions, with slope n for large |x|. So the function is convex and goes to infinity on both sides, so there is a unique minimum.
Now we need to find the x that minimizes h(x). We can do ternary search on x. Since the function is convex (and even unimodal), ternary search will find the minimum. However, note that h(x) is piecewise linear; ternary search on convex piecewise linear function works but might not be strictly convex; there might be a flat region? Possibly if there is an interval of x where the upper envelope and lower envelope have constant difference? But the function h(x) = U(x) - L(x) is convex and piecewise linear, and likely strictly convex unless some degenerate case, but we can handle by ternary search with enough iterations.
But we need to set search bounds. Since a_i in [-10^4,10^4], Q_i are between -2e9 and 2e9. The optimal x will likely be within [min(a_i), max(a_i)]? Let's examine. For x=0, h(0) = max Q_i - min Q_i (since P_i=Q_i). That's some number up to 2e9. For x far outside, h(x) is huge. So the minimum should be somewhere around where the lines cross. Could it be outside [min a_i, max a_i]? Possibly if the sequence is skewed? Consider a sequence with all large positive numbers: a_i=10^4. Then optimal x=10^4, which is within range. If all large negative: -10^4, optimal x = -10^4. So within range. For a sequence like [10000, -10000] maybe? Let's test: n=2, a=[10000, -10000]. We can compute: Q0=0, Q1=10000, Q2=0. We want to minimize max_i (Q_i - i x) - min_i (Q_i - i x). Let's find optimal x. Write P0=0, P1=10000 - x, P2=0 - 2x = -2x. So weakness = max(0, 10000 - x, -2x) - min(0, 10000 - x, -2x). We need to minimize over x. Try x around? If x=5000: P0=0, P1=5000, P2=-10000 => max=5000, min=-10000, diff=15000. If x=0: P0=0,P1=10000,P2=0 => max=10000,min=0,diff=10000. If x=10000: P0=0,P1=0,P2=-20000 => diff=20000. If x=-10000: P0=0,P1=20000,P2=20000? Actually -2x=20000, P1=10000 - (-10000)=20000, so all nonnegative, max=20000,min=0,diff=20000. So optimum maybe around x=0? But compute derivative? Possibly minimal diff is 10000 at x=0? But maybe there is better: x=3333.33? P0=0, P1=6666.67, P2=-6666.67 => diff=13333.33, larger. So x=0 gives 10000. Could we do x=500? P1=9500, P2=-1000, max=9500, min=-1000, diff=10500. So 0 seems best. So optimal x=0, which is within [min,max] = [-10000,10000]. So likely optimal x lies within [min a_i, max a_i]? But not necessarily: Consider sequence [10000, 10000, -20000]? hmm. Let's think: The lines L_i(x) = Q_i - i x. For i=0, L0=0 constant. For i>0, slopes -i. The upper envelope will be formed by lines with high Q_i and low slope? Actually for large x, lines with smaller i are higher because slope -i less negative. For x negative large, lines with larger i are higher. So the crossing point where the range is minimized likely occurs where the maximum and minimum lines are "balanced". The x that minimizes the range is something like the median of slopes? Actually this is reminiscent of minimizing max_i |Q_i - i x|? But we have range = max - min. However note that adding a constant to all P_i doesn't change range, but we have constant line i=0 = 0, so it's anchored.
We can find x that solves: max_i (Q_i - i x) = - min_i (Q_i - i x). Actually at optimum, the max and min are symmetric around zero? Not necessarily. But for convex range function, the minimum occurs when the slopes of the upper and lower envelope have opposite sign? Might be when the maximum equals the negative of the minimum? Actually if we shift the whole sequence by a constant (like adding c to all a_i, which changes Q_i by i*c, not simple). But note: P_i = Q_i - i x. If we define a constant shift: let x be chosen, then weakness = max_i P_i - min_i P_i. If we add a constant to all P_i, range unchanged. So we can't directly argue symmetry.
Nevertheless, ternary search with bounds covering plausible region is fine. Since a_i up to 1e4 in absolute, and n up to 200k, the slopes are up to 200k. The Q_i up to 2e9. The optimal x likely lies within [min_i a_i, max_i a_i]? Could be outside if one side is extreme? Let's try to derive bounds more rigorously.
We want to ensure that the optimal x lies within [L,R] such that h(L) and h(R) are greater than the minimum and the function is convex. We can set L = -20000? Actually a_i in [-10000,10000]. But x could be outside that range? Suppose all a_i are 10000; then optimal x=10000, which is exactly the max. If all a_i are -10000, optimal x=-10000. So bounds of [-20000,20000] might suffice? But consider a sequence where the a_i are all large positive except one huge negative? Actually they are bounded by 1e4. So the average might be between -1e4 and 1e4. However, is it possible that optimal x is outside that range? Let's try to construct: n=1, a1=10000. Then weakness = |a1 - x|. Minimized at x=10000, which is within range. For n=2: a = [10000, -10000]. We found optimal x=0, within [-10000,10000]. For n=2: a = [10000, 10000], optimal x=10000. So within. For n=2: a = [-10000, -10000], optimal x=-10000. So within.
What about n=3: a = [10000, 10000, -20000]? Sum? Actually a_i bounded by 1e4, but we can have -10000 and 10000. The average might be somewhere. But could optimal x be >10000? Suppose a = [10000, 10000, 10000] all 10000, optimal is 10000, equal to max. If we have all 10000 except one -10000, the average is less than 10000. The optimal x might be something like median? Actually we need to minimize max absolute subarray sum. This is similar to making the prefix sums as flat as possible. The x that minimizes range of (Q_i - i x) is something like the slope that makes the set of points (i, Q_i) have minimal vertical range when adjusting slope. This is like fitting a line through the points (i, Q_i) to minimize the range of residuals. That is essentially the "minimax" line fit (Chebyshev fit) for the points? Actually we are fitting a line with slope x and intercept 0? Because we subtract i x. So we are looking for slope x such that the points (i, Q_i) lie as close as possible to a line with that slope, but we only care about the vertical span, not the offset. Because adding an intercept (constant shift) would not change the range of residuals? Wait, if we had line y = x * i + c, then residual r_i = Q_i - (x i + c). The range of r_i = max(Q_i - x i - c) - min(...). For a given x, we can choose c to minimize the range; the minimal range over c is (max_i (Q_i - x i) - min_i (Q_i - x i))/2? Actually if we can choose c arbitrarily, we can center the residuals to make max and min symmetric, reducing the max absolute residual to half the range. But here we don't have a c; we have P_i = Q_i - i x, and weakness = max_i P_i - min_i P_i, which is exactly the range. However, note that weakness as defined originally as max segment absolute sum does not allow adding constant; we are subtracting x from each element, which is equivalent to shifting all a_i by the same constant, which changes the cumulative sums by -i x. There's no extra intercept term. So we cannot shift the whole sequence by another constant; we only subtract x from each element. So indeed weakness = range of P_i.
Thus the problem is to choose x to minimize the range of Q_i - i x. This is a one-dimensional Chebyshev approximation problem: find slope x such that the points (i, Q_i) are as "flat" as possible after removing slope x. This is like minimizing the vertical spread.
We can solve it by noting that the function h(x) = max_i (Q_i - i x) - min_i (Q_i - i x) is convex piecewise linear, with breakpoints at values where two lines intersect: Q_i - i x = Q_j - j x => x = (Q_i - Q_j)/(i - j). So the optimum occurs at some x equal to the slope of a line connecting two points (i, Q_i) and (j, Q_j). In fact, the minimax slope is such that the maximum positive deviation equals the maximum negative deviation (in absolute value). So at optimum, there exist indices i1, i2, i3, i4 such that the max is achieved at some indices and min at others, and the slopes of the supporting lines are such that... This is reminiscent of the problem of finding the slope that minimizes the range of points, which can be solved by computing the convex hull of the points (i, Q_i) and then finding the slope that makes the width in vertical direction minimal when rotating a line? But since we only vary slope, we might use ternary search as n is large.
Given that n is 200k, ternary search with 100 iterations each evaluating h(x) in O(n) is 20 million operations, which is fine in C++ (2e7). In Python, 20 million may be borderline but possibly okay with optimized code (use list and simple loop). But we need to be careful with time; 200k * 100 = 20 million, which in Python might be around 0.2 seconds? Actually 20 million simple arithmetic operations might be ~0.5-1 second, acceptable if well-written. But we also need to handle double precision. However, typical time limit on Codeforces (this is a Codeforces problem, 319B?) is 1-2 seconds. Python 20 million may be too slow. Could we reduce iterations? Since we need 1e-6 absolute or relative error, we need high precision. But the answer is up to 2e9, so absolute error 1e-6 is fine. Ternary search on double with range maybe [-20000,20000]? Actually x could be outside that, but we can bound. Let's find proper bounds.
We need to guarantee that the minimum lies within our search interval. Since a_i ∈ [-10^4, 10^4], Q_i ∈ [-2e9,2e9]. Consider x = (max_i a_i + min_i a_i)/2? Not sure. The optimal x likely lies within the convex hull of the points (i, Q_i). The slopes (Q_i - Q_j)/(i-j) are bounded by something. The maximum possible slope magnitude? Since Q_i changes by at most 10^4 per step, the difference Q_i - Q_j is at most 10^4 * (i-j) in absolute value. Actually |a_i| ≤ 10000, so |Q_i - Q_j| ≤ 10000 * |i-j|. So the slope between any two points is bounded by 10000 in absolute value. However, the optimal x might be exactly such a slope? Yes, the breakpoints are of that form. So x is between min and max of (Q_i - Q_j)/(i-j) which are in [-10000,10000]. Wait, is that always true? Since each a_i is bounded by 10000, the incremental difference a_i = Q_i - Q_{i-1} is between -10000 and 10000. So the average slope over any interval is between -10000 and 10000. But the breakpoints x where two lines intersect are of that form. However, the optimal x might not be exactly a breakpoint if there is a flat region? But it will be some value where the subgradient includes zero. It's plausible that the optimal x lies within the interval [min a_i, max a_i]? Actually consider n=2, a=[-10000,10000], Q0=0, Q1=-10000, Q2=0. The slopes: between (0,0) and (1,-10000) => -10000; between (0,0) and (2,0) => 0; between (1,-10000) and (2,0) => 10000. The breakpoints are -10000, 0, 10000. The optimal x we found 0. So indeed within [-10000,10000]. For n=3, a=[-10000, -10000, 20000]? Actually a_i bounded by 10000, so max increment is 10000. Let's consider worst-case: a1=10000, a2=10000, a3=-20000? But a3 cannot be -20000 because bound is 10000. So maximum absolute is 10000. So the slopes between any two points are bounded between -10000 and 10000. However, could the optimal x be outside that? Let's try a case where a_i are all 10000 for first half and -10000 for second half. For n=4: a=[10000,10000,-10000,-10000]. Compute Q:0,10000,20000,10000,0. Points: (0,0), (1,10000), (2,20000), (3,10000), (4,0). The slopes between points range from? The extreme slopes: between (0,0) and (2,20000) => 10000; between (0,0) and (4,0) => 0; between (2,20000) and (4,0) => -10000. So again within [-10000,10000]. So it appears that all slopes (Q_i - Q_j)/(i-j) are averages of a_k over that interval, hence are between min a_k and max a_k. Indeed, (Q_i - Q_j)/(i-j) = average of a_{j+1..i}. Since each a_k ∈ [min_a, max_a], the average lies in that interval. Therefore any breakpoint x (intersection of lines i and j) equals that average, hence lies between min_a and max_a. However, the optimal x might be at a point that is not a breakpoint? But if the optimal x lies in a region where the active lines for max and min are constant, the derivative is constant; the minimum occurs where derivative crosses zero. The derivative of h(x) = U'(x) - L'(x), where U'(x) is the slope of the upper envelope at x (which is -i for some active line) and L'(x) is slope of lower envelope (which is -i for some active line). At optimum, we have U'(x) ≤ 0 ≤ -L'(x)? Actually since h is convex, the subgradient at minimum contains 0. The derivative from left and right: Since U is max of lines with slopes -i, U'(x) is piecewise constant non-increasing (since slopes negative). L is min of lines, L'(x) is also piecewise constant non-increasing? Actually L is min of lines, each with slope -i. So L'(x) is the slope of the line that is currently minimum; as x increases, the minimum line may switch to one with more negative slope? Let's think: L(x) = min_i (Q_i - i x). Since slopes -i are decreasing with i (more negative for larger i). For large x, the smallest (most negative) values come from lines with larger i (more negative slopes). As x increases, lines with steeper negative slopes become even smaller. So the lower envelope is composed of lines with slopes that are decreasing (more negative) as x increases. So L'(x) is non-increasing (becoming more negative). The derivative of L is the slope of the active line, which is -i, so it's negative and can be more negative as x increases. Similarly, U'(x) is the slope of the active line for the max, which is also negative but perhaps less negative (since the max line for large x will be one with small i, slope 0 or -1? Actually U(x) = max_i (Q_i - i x). For large x, the max will be from line with smallest |slope| (i minimal, i=0 gives slope 0). So U'(x) will be 0 from i=0 eventually. As x decreases, other lines become max. So U'(x) is also non-increasing? Let's check: For x very negative, the max line is from large i (since -i x becomes large positive). So U'(x) = -i for some large i, which is negative (large magnitude). As x increases, U'(x) increases (becomes less negative) because the active line may switch to one with smaller i. So U'(x) is actually increasing with x? Since slopes -i become less negative as i decreases. But we can just analyze h'(x) = U'(x) - L'(x). At optimum, h'(x) should be 0 (or cross zero). Since U'(x) is increasing? Actually U is convex, so its derivative is non-decreasing? Wait, convex function has increasing derivative. Since U(x) is convex (max of linear functions), its derivative is non-decreasing (since convex). But we argued U'(x) for large x is 0, for small x is negative; as x increases, derivative goes from negative to 0, so indeed non-decreasing. L(x) is concave? Actually L(x) is min of linear functions, which is concave. So its derivative is non-increasing. But we can think of -L(x) is convex, and derivative of -L is -L'. So L' is non-increasing, meaning -L' is non-decreasing. h = U + (-L) is convex. Then h' = U' + (-L')'? Actually derivative: h' = U' + (-L)' = U' - L'. Since both U' and -L' are non-decreasing, h' is non-decreasing (makes sense for convex). So h' is non-decreasing. At the minimum, h' crosses from negative to positive.
Now, U'(x) is the slope of the active upper line, which is some -i_u (negative or zero). L'(x) is slope of active lower line, which is some -i_l (negative, maybe more negative). So h'(x) = -i_u - (-i_l) = i_l - i_u. Since i_l and i_u are integers between 0 and n. At optimum, we should have i_l ≈ i_u? Actually h' = i_l - i_u. Since i_l and i_u are indices of active lines for min and max. For large x, U'=0 (i_u=0), L' negative large (i_l large), so h' = i_l - 0 > 0 (positive). For x very negative, U' negative large (i_u large), L' maybe? For x very negative, the max line comes from large i (i_u large). The min line? For x very negative, all lines Q_i - i x: as x → -∞, -i x = i|x| huge positive. So all lines go to +∞. The minimum among them will be the one with smallest i because its growth is slowest? Actually if x → -∞, consider two lines: line i: intercept Q_i, slope -i; since x is negative large, -i x = i * |x|, so line with smaller i grows slower, thus has smaller value. So min_i (Q_i - i x) for x → -∞ is achieved by the smallest i, which is i=0 (value 0). Also i=0 gives 0, others give large positive, so min is 0 from i=0. So L(x) is from i=0 (constant 0). Then L'(x)=0. U(x) is from some large i (since large i gives larger value). So U'(x) = -i_u, negative. Then h' = U' - L' = -i_u - 0 = -i_u < 0. So h' negative for very negative x, positive for very positive x. At optimum, h' crosses zero. Since h' is integer step changes, there might be an interval where h'=0. The condition h'=0 means i_l = i_u. That is, the active indices for max and min are equal? But can that happen? Possibly when the upper envelope and lower envelope come from the same line? But then range would be zero? Actually if the same line gives both max and min, then all points lie on that line, so range zero. That would be ideal but rarely. Typically, at optimum, i_l > i_u? Let's compute h' = i_l - i_u. For x very negative, i_l=0 (min line i=0), i_u large, so h' = 0 - large <0. For x very positive, i_l large, i_u=0, h' = large - 0 >0. So as x increases, i_l increases (min switches to larger indices) and i_u decreases (max switches to smaller indices). At some x, i_l becomes > i_u. When i_l = i_u? That would mean the max and min are from the same line, implying the range is zero? Actually if max and min are from same line, then all other lines are between them, and the max equals the min, so all P_i equal, range zero. That can happen only if all points lie on a line, i.e., Q_i = i*x for some x. That means a_i = x constant. So if not constant, i_l and i_u will not be equal; the crossing of h' from negative to positive will occur at a point where h' jumps from negative to positive, possibly skipping zero. The minimum will be at the point where the subgradient contains zero, i.e., there exists some x where left derivative ≤ 0 ≤ right derivative. Since h' is non-decreasing and piecewise constant, the minimum occurs at the x where h' changes sign, which could be an interval if h'=0 on an interval. But if h' jumps from negative to positive at a point, then at that point the subgradient includes values between left and right derivatives, so 0 is in subgradient, so that point is optimal. That point is typically where the upper and lower envelope have equal "support" from two lines? Actually we can find x such that the maximum deviation above and below are equal? Since h(x) = max_i P_i - min_i P_i. If we could shift by a constant, we'd set max and min symmetric. But here we cannot shift. However, maybe the optimal x satisfies that the max positive deviation from some reference equals the max negative deviation, but reference is not zero. Actually note that if we add a constant to all P_i, range unchanged, but we cannot add constant. However, we could think of aligning the center. There might be a relationship: at optimum, the line with slope x that best fits the points yields that the maximum residual and the negative of the minimum residual are equal? Not necessarily because we cannot adjust intercept. But we can consider intercept as part of the constant? Actually we could define c = - (max_i P_i + min_i P_i)/2. Then the range is 2 * max_i |P_i + c|. But we cannot adjust c, it's determined by x. So the problem is to choose x to minimize range, not to minimize max absolute residual with free intercept. So it's different.
But anyway, ternary search works.
We need to set search bounds. Since all slopes between min_a and max_a, the optimal x will also be between min_a and max_a. Proof: The function h(x) is convex and tends to infinity as |x|→∞. Its derivative for x < min_a: Let's examine derivative signs more carefully. Consider x less than min_a (the minimum of a_i). For x < min_a, we have a_i - x > a_i - min_a ≥ 0, so b_i > 0 for all i? Actually if x < min_a, then a_i - x > 0 for all i (since a_i ≥ min_a > x? Wait if x < min_a, then for each i, a_i - x > a_i - min_a ≥ 0? Since a_i - min_a can be zero for the minimum element, but a_i - x = (a_i - min_a) + (min_a - x) > 0 because min_a - x > 0. So b_i > 0. Then all b_i > 0, so the sequence b is all positive. Then P_i = sum_{1..i} b_i is strictly increasing? Actually if all b_i > 0, then P_i is increasing. So max_i P_i = P_n, min_i P_i = P_0 = 0. So h(x) = P_n. Now P_n = sum_{i=1..n} (a_i - x) = (sum a_i) - n x. As x decreases, P_n increases. So for x < min_a, h(x) = (sum a_i) - n x. This is linear with slope -n. Its derivative (left derivative) is -n (since as x increases, h decreases). Actually for x sufficiently low, h(x) is given by that line? Not necessarily: if all b_i positive, then indeed max = P_n, min = 0. But also need to consider if any P_i could be negative? No, because all b_i positive, cumulative sums are positive increasing from 0. So yes. So for x < min_a, h(x) = (sum a_i) - n x. That's a line with slope -n. For x > max_a, then x > max_a, so a_i - x < 0 for all i (since a_i ≤ max_a < x). Then all b_i negative. Then P_i are decreasing (starting at 0, then negative). So max_i P_i = 0 (at i=0), min_i P_i = P_n (most negative). So h(x) = 0 - P_n = -P_n = -[ (sum a_i) - n x ] = n x - sum a_i. That's a line with slope +n. So for x > max_a, h(x) = n x - sum a_i. So indeed outside the interval [min_a, max_a], h(x) is linear with slope magnitude n. Inside that interval, h(x) is more complicated but is convex and lies below these linear extrapolations? Probably. So the optimal x will lie within [min_a, max_a] because if x is less than min_a, h(x) is decreasing as x increases (since slope -n <0) until we hit min_a; so moving to larger x reduces h. Similarly for x > max_a, h(x) is increasing as x increases (slope n >0). So the minimum must be in the region where h is not monotonic, which is within [min_a, max_a]. So we can safely set L = min_a, R = max_a. However, is it possible that the optimal x is exactly at min_a or max_a? Possibly if the sequence is monotonic? But that's okay; ternary search will converge to that boundary if it's the minimum. So we can set bounds to min_a and max_a.
But note: If all a_i are constant, then min_a = max_a, and the interval is a point. Then ternary search with equal bounds works (we can handle separately or just set L=R and skip). But we can set L = min_a, R = max_a.
Now we need to perform ternary search on a convex function. Since h(x) is convex and unimodal, ternary search on a continuous domain works. However, the function is piecewise linear; ternary search will converge but we need to be careful about precision and number of iterations. Typically we can run for a fixed number of iterations (like 80-100) and then compute h at the final x. But we might need to output the minimal weakness, not the x. So we can just evaluate h at the final x. However, the function is piecewise linear; ternary search might get stuck if the function has flat regions. But that's okay; the minimum value is still found. But the search might give a point not exactly at the optimum but close enough that h is close to minimum. Since we have convex function, the error in function value after enough iterations will be small.
Alternatively, we could compute the minimum directly via binary search on the answer? Another approach: Because h(x) = max_i (Q_i - i x) - min_i (Q_i - i x) = max_i ( -i x + Q_i) - min_i ( -i x + Q_i). This is a difference of two functions that are max of lines. The minimum can be found by solving a linear programming problem: minimize t such that there exists x with max_i (Q_i - i x) - min_i (Q_i - i x) ≤ t. But t is the weakness. That's equivalent to: there exists x such that for all i, Q_i - i x ≤ M, and for all i, Q_i - i x ≥ m, and M - m ≤ t. That is: m ≤ Q_i - i x ≤ M, with M - m ≤ t. Minimizing t is like finding the smallest width strip that contains all points (i, Q_i) when we are allowed to choose slope x. This is similar to the problem of "minimum width strip" with fixed slope? Actually we are allowed to rotate the line (with slope x) but the strip is vertical? Wait: The condition is: For a given x, we consider the vertical positions of points after subtracting i x. So we are taking the set of points (i, Q_i) and projecting onto a direction? Actually we subtract i x, which is like rotating the coordinate system: define new y' = y - x i. Then we look at the range of y' values. We want to choose x to minimize the vertical span. This is equivalent to finding the slope that minimizes the vertical extent of the point set. This is a known problem that can be solved by computing the upper and lower convex hull and then finding the slope that minimizes the vertical distance between two supporting lines with that slope. It can be solved in O(n log n) by rotating calipers? However, n=200k, we could do ternary search O(n log precision) which is simpler.
Given constraints, O(n * iter) with iter=100 yields 20 million operations; Python might be okay if optimized with simple loops and using floats. But 20 million floating multiplications and comparisons could be borderline but likely passes if coded efficiently (maybe 1.2 seconds?). However, we need to be careful with input size and using sys.stdin.read.
We can reduce number of iterations: Since we need absolute error 1e-6 on answer, and the function's range is up to 2e9, the relative error might be small. Ternary search on convex function converges exponentially. The width of interval halves each iteration? Actually ternary search reduces interval by factor 2/3 each iteration (since we take points at 1/3 and 2/3). After k iterations, interval length is (2/3)^k * initial range. Initial range: max_a - min_a ≤ 20000. (if a_i within -10000..10000). Actually min_a - max_a difference ≤ 20000. So after 100 iterations, (2/3)^100 is astronomically small, far beyond 1e-6. But we need to evaluate function at each step; each evaluation O(n). 100 iterations = 20 million. Might be okay. But we can maybe do 60 iterations: (2/3)^60 ~ (0.6667)^60 ~ 1e-10, times 20000 ~ 2e-6, good. So 60 iterations may suffice. Let's compute: log(1e-6/20000)/log(2/3) = log(5e-11)/log(0.6667) ≈ (-23.5)/(-0.405)=58. So 60 iterations enough. So we can do 60-80.
Alternatively, we can use binary search on the derivative? But ternary search is fine.
But note: The function is piecewise linear; the exact minimum is at a breakpoint. We might compute the answer exactly by enumerating candidate x from breakpoints? There are O(n^2) breakpoints, but maybe we can reduce to O(n) by considering that the upper envelope is defined by the upper convex hull of points (i, Q_i) when considering lines with slopes -i? Wait, the lines are L_i(x) = Q_i - i x. For max envelope, we need the lines with slope -i. For min envelope, we need lines with slope -i as well. The upper envelope of lines with slopes -i corresponds to the upper convex hull of points (i, Q_i) when considering something? Actually, the value of line L_i at x is Q_i - i x. This is like the dot product? Alternatively, we can think of x as the slope when we view the points. The upper envelope U(x) = max_i (Q_i - i x) is the Legendre transform (convex conjugate) of the set of points? It is essentially the support function. The function h(x) = U(x) - L(x). The minimum occurs when the supporting lines for U and L have some relation. It could be solved by binary search on answer? But ternary search is simpler.
However, we must also consider that evaluating h(x) in O(n) might be a bit heavy but okay.
But there is a nuance: For a given x, computing max_i (Q_i - i x) and min_i (Q_i - i x) can be done in one pass. We need to compute prefix sums Q_i first. But note: Q_i are integers up to 2e9, so using floats for multiplication by x (double) is fine. x is double. We'll compute Q_i as integers (maybe 64-bit), but then convert to double for subtraction? We can compute in double: val = Q_i - i * x. i up to 200k, x up to 20000, i*x up to 4e9, still within double precision (53 bits ~ 9e15). So fine.
Thus algorithm:
- Read n, array a[1..n].
- Compute prefix sums Q[0..n]: Q[0]=0; for i in 1..n: Q[i] = Q[i-1] + a[i]. Use 64-bit integer (Python int is arbitrary precision).
- Set L = min(a), R = max(a). (If L==R, answer = 0? Actually if all a equal to c, then weakness = 0 for x=c. So answer 0. So we can output 0.0.)
- Define function weakness(x):
- Initialize min_val = 0.0 (for i=0) and max_val = 0.0.
- For i from 1 to n: val = Q[i] - i * x update min_val = min(min_val, val) update max_val = max(max_val, val)
- Return max_val - min_val.
- Perform ternary search on continuous x in [L,R] to find minimum of weakness(x). Since function is convex, we can use standard ternary search for real numbers: for iteration in range(100): m1 = L + (R - L)/3 m2 = R - (R - L)/3 f1 = weakness(m1) f2 = weakness(m2) if f1 < f2: R = m2 else: L = m1 After loop, x_opt = (L+R)/2, answer = weakness(x_opt). Or we can keep track of min f during search. Note: Because of floating point errors, we may want to use a fixed number of iterations rather than while (R-L) > eps.
But we must ensure that the function is indeed convex. Yes.
Edge Cases: The function may have flat regions; ternary search will converge to some point in the flat region and the value will be correct.
Now, what about potential overflow? In Python, using int for Q_i is safe. ix uses float multiplication; but Q_i is int, so we need to convert to float: val = Q[i] - i * x. Since ix is float, Python will convert Q[i] to float automatically? Python supports mixed arithmetic; int - float yields float. That's fine. But we might want to use floats from the start to avoid conversion overhead? Could precompute Q_i as floats? Might be slower? We'll keep ints.
But careful: For large n and many iterations, doing Python loops with 200k each time 100 times is 20 million loops. In each loop we do a float multiplication (i*x) and subtraction and min/max. This might be around 0.2-0.3 seconds? Actually Python loops are slower; 20 million operations might take 1-2 seconds, maybe more. Let's estimate: On Codeforces, Python can handle ~50 million simple operations per second? Actually typical Python can do about 30-50 million simple integer ops per second? Not exactly; it's slower. A simple loop with a few operations might run at 20-30 million per second on PyPy? But we need to be safe. Using PyPy might be okay. Many solutions in Python for this problem use ternary search with 100 iterations and pass.
But we can attempt to reduce number of iterations further, maybe 60-80. 60 iterations * 200k = 12 million, which is better.
We could also use a more efficient method: Since h(x) is convex piecewise linear, we could find the optimum by binary searching on derivative, but that would require evaluating something like the subgradient, which can be computed by checking which indices achieve max and min? Possibly we can compute the derivative sign by evaluating which side of optimum we are on: For a given x, we can compute the indices that give max and min. Then the derivative h'(x) = (slope of max line) - (slope of min line). Actually the subgradient at x includes values between left and right derivatives; but we can compute the right derivative perhaps. If we could compute the subgradient, we can binary search on x where derivative changes sign. However, evaluating derivative exactly is tricky due to multiple active lines. But we can compute a value that indicates whether we are left or right of optimum: At optimum, the maximum of P_i and -minimum of P_i are balanced? Actually recall weakness = max(P_i) - min(P_i). Let M(x) = max_i P_i, m(x) = min_i P_i. The derivative from right: M'(x) is the slope of the line achieving max at that x (if unique), similarly m'(x) is slope of line achieving min. So h'(x) = M'(x) - m'(x). Since M'(x) is negative (or zero) and m'(x) is negative (or maybe also negative? Actually m'(x) could be negative or positive? Let's think: m(x) = min_i (Q_i - i x). For x large, the min line is from large i (since more negative slope), so slope is -i, negative. For x small, min line is from i=0, slope 0. So m'(x) is non-increasing, starts at 0 for x very negative, then becomes negative as x increases. Actually for x very negative, min is from i=0 with slope 0, so m'(x)=0. For x very positive, min from i=n with slope -n, negative. So m'(x) is ≤ 0 for all x? Possibly yes, because min of lines with slopes ≤ 0: each line slope is -i ≤ 0. So the min envelope's derivative is also ≤ 0. So both M' and m' are ≤ 0. Then h' = M' - m' can be negative (if M' < m') or positive (if M' > m'). Since M' is more negative than m'? Actually for x very negative, M' is negative (large magnitude), m' = 0, so h' negative. For x very positive, M' = 0, m' negative, so h' positive. So we could compute the subgradient by identifying the slopes of the active lines. But that requires knowing which lines are active at a given x, which might be found by linear time scanning? Could compute the indices i that give max and min for the given x. However, there could be multiple; but we can compute the maximum P_i value and also the largest i among those achieving max? Actually we can compute the right derivative by considering the maximum P_i and the corresponding slope? But if multiple indices achieve the same max, the derivative could be any value between their slopes? For convex max function, the subgradient at x is the convex hull of slopes of active lines. However, we can compute a value that tells us if x is to the left or right of the optimum by checking the relationship between f(x) and g(x) (the max subarray sum and -min subarray sum). Actually note: weakness = max(f,g). At optimum, f(x) and g(x) are as close as possible. Since f decreasing, g increasing. The optimum is where f(x) ≈ g(x). If f(x) > g(x), then we are to the left of the optimum? Let's see: For x very negative, f large, g small? Actually for x very negative, b_i are large positive, so f (max subarray sum) is large positive, g = - min subarray sum? Since all positive, min subarray sum is smallest positive, so g = - positive = negative? Wait earlier we said g(x) = - min_subarray_sum(b). If all b positive, min_subarray_sum >0, so g is negative. But weakness is max(f,g) and g negative, so weakness = f. But is g negative? Actually - min_subarray_sum: if min_subarray_sum >0, then -min_subarray_sum is negative. However, we defined g as - min_subarray_sum(b). But earlier we had weakness = max(f,g). If g negative, then max(f,g) = f if f positive. So indeed for x very negative, f large positive, g negative, so weakness = f. For x very positive, b negative, f (max subarray sum) might be negative or zero? Actually if all b negative, the max subarray sum is the maximum element (least negative) which is negative, so f negative. g = - min_subarray_sum(b). Since min_subarray_sum is most negative (large magnitude), -min is large positive. So weakness = g. So at optimum, we expect f and g to be equal? Possibly. Because f decreasing, g increasing. The function h = max(f,g) is minimized when f=g (if they cross). If they don't cross exactly, the minimum occurs at the point where f=g? Actually if they cross at a point, then h = f = g at that point. If they never cross (i.e., there is a gap), then the minimum would be at the boundary of the region where one dominates? But since f decreasing from +∞ to -∞? Actually f(x) for x→ -∞: f(x) ~ -n x? Wait: For x→ -∞, b_i = a_i - x ≈ -x (since x negative large, -x positive large), so each b_i ~ -x. So sum of whole array = n * (-x) + sum a_i. Since -x huge, f(x) = max subarray sum will be sum of whole array because all positive, so f(x) ≈ -n x (dominant). That goes to +∞. For x→ +∞, b_i negative large, so the max subarray sum will be the maximum element? Actually all negative, max subarray sum is the maximum (least negative) which will be something like a_i - x, the largest among them. As x→∞, a_i - x ≈ -x, so the maximum of these tends to -∞? Wait if x large positive, a_i - x is negative large; the maximum among them (i.e., the least negative) will be the one with largest a_i, say max_a, so max subarray sum ≈ max_a - x, which → -∞. But is that the maximum subarray sum? For all negative numbers, the maximum subarray sum is the maximum element (since any subarray longer than 1 will be more negative). So f(x) → -∞ as x→∞. Actually f(x) → -∞ linearly with slope -1? Not exactly, but tends to -∞. Meanwhile g(x) = - min_subarray_sum(b). For x→ -∞, b all positive, min_subarray_sum is the minimum element (since all positive), which is ≈ -x? Actually min element is a_min - x. Since x→ -∞, -x → +∞, so min element → +∞, so g(x) = -min_subarray_sum → -∞ (because min_subarray_sum positive large). So g(x) → -∞ as x→ -∞. For x→ +∞, b all negative, min_subarray_sum is the sum of the whole array? Actually for all negative, the minimum subarray sum is the most negative, which could be the sum of the whole array if all negative? But if all b negative, the most negative sum is the sum of the whole array (since adding more negatives makes it more negative). So min_subarray_sum ≈ n*( - x ) + sum a_i, which tends to -∞, so -min_subarray_sum → +∞. So g(x) → +∞ as x→ +∞. So f(x) goes from +∞ (x→ -∞) down to -∞ (x→ +∞); g(x) goes from -∞ up to +∞. Both are continuous? f is convex? Actually f is maximum of decreasing linear functions, so it's convex, continuous, piecewise linear. g is convex? Actually g = max of increasing lines, also convex and continuous. So f and g are continuous. Therefore by Intermediate Value Theorem, they must cross at some point x0 where f(x0)=g(x0). That crossing point is unique? Not necessarily, but there will be at least one. At that crossing, h = f = g. And because f decreasing, g increasing, for x < x0, f > g? Let's check: at x very negative, f large positive, g negative, so f > g. At x very positive, f negative, g large positive, so g > f. So by monotonicity (f decreasing, g increasing), there is exactly one crossing point (if they are strictly monotonic at that region). But could there be a flat interval where they are equal? Possibly if there is a range of x where f and g are constant and equal? That would mean that for a range of x, the maximum subarray sum equals the negative minimum subarray sum and both are constant. That would require some symmetry, maybe if the sequence is constant? Actually if constant, f(x)=max subarray sum = n*(c-x) if c-x>0? Wait if constant c, then b_i = c-x. For x < c, all b positive, f = n*(c-x), g = - (c-x) (since min subarray sum = c-x, the smallest element? Actually min subarray sum = c-x (since all positive, smallest sum is the smallest element which is c-x, but if length 1, it's also c-x). So g = -(c-x). So f and g are not equal unless n*(c-x) = -(c-x) => (c-x)(n+1)=0 => c-x=0, i.e., x=c. At x=c, f=0, g=0. So only at one point. So crossing is unique.
Thus optimum occurs at the unique x where f(x)=g(x). So we could binary search for x such that f(x) - g(x) changes sign. This might be more efficient because we only need to compute f and g (or compute weakness and also compare f and g) and binary search until interval small enough. However, we need to minimize max(f,g) which at crossing equals f=g. So finding x where f(x)=g(x) yields the optimal. But we need to ensure that at that point, max(f,g) is minimized. Since f decreasing, g increasing, the function h(x)=max(f,g) is minimized exactly at the crossing (or the point where f and g are as close). So we can binary search on x to find the point where f(x) <= g(x) or f(x) >= g(x). Then after binary search, we can compute h at the found x. But careful: f and g are not necessarily strictly monotonic, but they are non-increasing and non-decreasing respectively. So we can binary search on the condition f(x) >= g(x). For x very low, f >= g. For x very high, f <= g. So we can find the point where they cross. However, there might be a range where f(x)=g(x) over an interval; then any x in that interval gives the same h. So binary search will converge to some point within that interval.
Thus we can perform binary search on x to find the crossing. Each iteration we compute f(x) and g(x) via Kadane? But we can compute f and g directly from P_i: f(x) = max_{seg} sum = max_{0<=l<r<=n} (P_r - P_l) = max_i P_i - min_i P_i? Wait that's the weakness, not f. Actually f(x) = max subarray sum of b, which is max_{0<=l<r<=n} (P_r - P_l). But we can compute this in O(n) by scanning and keeping track of min prefix: max_subarray_sum = max_{r} (P_r - min_{l<r} P_l). Similarly, min_subarray_sum = min_{r} (P_r - max_{l<r} P_l) or just keep track accordingly. But we can also compute f(x) and g(x) separately. However, to compute both we need two passes? Actually we can compute max_subarray_sum and min_subarray_sum in one pass: maintain current max ending here and min ending here. Or we can compute directly from P_i: For max subarray sum, compute max difference P_r - P_l with l<r. That's max_{r} (P_r - min_{l<r} P_l). For min subarray sum, it's min_{r} (P_r - max_{l<r} P_l). So we can compute both in one pass: traverse i from 1 to n, maintain min_prefix = min(P_0,...,P_{i-1}) and max_prefix = max(P_0,...,P_{i-1}), then max_sub = max(max_sub, P_i - min_prefix), min_sub = min(min_sub, P_i - max_prefix). Initialize with P_0=0. Complexity O(n).
But we also need to compute f and g, and we need to decide binary search condition: if f(x) > g(x), then x is too low (since f decreasing, g increasing). So we need to increase x. If f(x) < g(x), x too high, decrease x. If equal, we can stop.
Binary search on double may require many iterations as well (like 80). But we can also compute the exact x from the crossing by solving equations? Since f and g are piecewise linear, binary search will converge to the optimal point. However, we need to output the minimal weakness, not x. So after binary search, we can evaluate h(x) = max(f,g) (or directly compute weakness from P_i). That also yields the answer.
Binary search may be slightly more efficient because we don't need to evaluate two function evaluations per iteration (ternary uses two). But binary search also requires two function evaluations? Actually binary search on condition requires evaluating f(x) and g(x) (which can be done together in one pass). Ternary search requires two evaluations per iteration (two passes) to compare f1 and f2. So binary search uses one pass per iteration, ternary uses two passes per iteration. So binary search is about twice as fast for same number of iterations. However, we need to ensure convergence to the minimum value with high precision. Binary search on the crossing finds x where f ≈ g, but the resulting h may be close to the optimal h. Since h is convex and minimized at crossing, if we find x with f(x) and g(x) nearly equal, then h(x) is near optimal. But we need the answer to 1e-6 absolute/relative error. The function h is Lipschitz with slope at most n near optimum? Actually near optimum, the derivative