Theorem 8.2 ([1]})  
Let Algorithm REF  process a stream \((P,w)\)  of at most \(n\)  points. Let \(R_i\)  denote the prefix of the stream received before the end of phase \(i\) , and let \(K_i\)  and \(L_i\)  be their final values from the algorithm (which are never modified after phase \(i\) ). With probability at least \(1 - \frac{1}{n}\) , the following statements all hold after processing each point:
