Before revision:  Although our space usage is O(n), we work in the presence of an adaptive adversary  .
After revision:  Although our space usage is O(n), we work in the presence of an adaptive adversary , and we show that \Omega(n) space is required when adversary is adaptive .