Implement PAVA spend-smoothing under no-borrowing constraint

You are given a length-65 vector profit[1..65] of yearly discretionary income (can be treated as nonnegative real numbers). We want a spending plan s[1..65] that is as even as possible over time while not spending future money. Formally, solve: minimize Σ_{t=1..65} (s_t − profit_t)^2 subject to s_1 ≤ s_2 ≤ … ≤ s_65, s_t ≥ 0, and Σ_{i=1..t} s_i ≤ Σ_{i=1..t} profit_i for all t (no borrowing), with Σ_{t} s_t = Σ_{t} profit_t (no money left unallocated). 1) Show that the solution is the isotonic L2 regression of profit under a nondecreasing constraint (Pool-Adjacent-Violators Algorithm, PAVA) and explain why it respects no-borrowing when mass is only shifted forward. 2) Implement an O(n) PAVA (R or Python), returning s and the block structure. 3) Using set.seed(12345) and profit ~ rnorm(65, mean=1000, sd=100) (clip at 0 if needed), run your algorithm, report Σ(s_t − profit_t)^2, verify monotonicity, and demonstrate that cumulative spend never exceeds cumulative profit at any prefix. 4) Compare against a naive iterative averaging method (like repeatedly averaging decreasing runs) on both correctness and runtime.