A pipeline reports the net throughput (which may be negative) of each of n consecutive stages. A mandatory inspection happens at stage p (0-indexed), so any run you consider must include stage p.
Find the maximum sum over all non-empty contiguous runs that contain index p. This equals the best sum you can extend to the left of p (ending exactly at p) plus the best non-negative extension to the right of p. This is the "crossing run" combination at the heart of the divide-and-conquer maximum-subarray method, evaluated at a fixed anchor.
Input format
Line 1: two integers n and p (0-indexed anchor, 0 <= p < n).
Line 2: n space-separated integers, the per-stage throughputs.
Output format
A single integer: the maximum sum of a contiguous run that includes index p.
Constraints
- 1 <= n <= 100000
- 0 <= p < n
- -1000000000 <= each throughput <= 1000000000