Efficiently find elements which are out of place in an otherwise sorted list
If I'm understanding the problem correctly, you have a list that's supposed to be monotonically increasing (aka sorted), and need to discard any items that break this rule. The trick being, an item that's greater than its predecessor might still be invalid, if its predecessor was invalid.

I'm going to make one additional assumption: the first row is always correct. (Because I don't see any way it could be wrong, and if there is, you can check that by hand in $O(1)$ before running.)

If this is correct, then here's how I would solve it.

define FlagBadItems(timestamps[0..n]):
    last_good = timestamps[0]
    for item in timestamps[1..n]:
        if item &lt; last_good:
            flag item as bad
        else:
            last_good = item


In other words, we keep a variable called last_good which is the last timestamp we know to be correct. Each row is considered bad if it's lower than last_good. If it's bad, last_good remains the same, otherwise, last_good is updated.

This runs in $O(n)$, since there's a single run through the data set, with constant work per iteration. The space complexity is $O(1)$ for overhead plus $O(n)$ for your input list.