Before revision:  More precisely, we present a randomized algorithm that performs each operation in time \tilde O(n^{ 4 / 5 }) and after each update, reports the answer to the LIS problem correctly with high probability.
After revision:  More precisely, we present a randomized algorithm that performs each operation in time \tilde O(n^{ 4 / 3 }) and after each update, reports the answer to the LIS problem correctly with high probability.