Before revision: )\left({\varepsilon^2}\cdot n^{1-2/p}}\right) 
After revision: )\left({\varepsilon^2}\cdot n^{1-2/p}}\right) for one-pass insertion-only streams. Our results separate the complexity of this problem both between random and non-random orders, as well as one-pass and multi-pass streams.