That assumes you're providing the output as a list of elements. Since it's a contiguous sequence, you can uniquely identify a particular output as a tuple (start, length). So you can get a constant-time solution if you're allowed to assume the input is valid (and have a constant-time way of getting the length of the input, I guess).

On the other hand, checking to ensure that the input represents a valid sequence is going to be O(n) in the size of the input no matter what you do...