Increasing Triplet Subsequence

Maintain first and second, initially positive infinity. For each x, if x is at most first, set first=x; else if x is at most second, set second=x; otherwise x is greater than both and forms an increasing triplet. The invariant is not that first and second are the earliest values, but that they are the smallest achievable tails of an increasing subsequence of length one and two seen so far. Replacing first later can still help because the existing second may have appeared after an earlier valid first; the algorithm only needs existence, not explicit index reconstruction. Use <= in the updates so equal values do not count for a strictly increasing relation. If asked for the actual indices, store candidate positions more carefully or use a longer-subsequence reconstruction approach. Test fewer than three elements, descending input, duplicates, and a triplet with a late smaller first. Time is O(n), space O(1).