Give an algorithm with better than O(n^2) time complexity for finding the longest strictly increasing consecutive subsequence of a sequence of n numbers. Argue that any algorithm for this problem must examine all elements in the array in the worst case, thus has (n) lower bound.

Example: For the sequence 7, 8, 10, 2, -3, 3, 6, 7, 55, 41, 76, the desired subsequence has length 5 and is -3, 3, 6, 7, 55.