Firstly without loss of generality, we can assume that $$$0 \le a_i \le n - 1$$$, by coordinate compression.

Let's try fixing the one pair that is out of order in the subsequence. Define $$$l_x, r_x$$$ to be the longest increasing sequence ending at index $$$x$$$ and the longest increasing sequence starting from index $$$y$$$ respectively. These values can be computed for all $$$x$$$ using a segment tree in one pass. Then the answer to the problem is $$$\max_{i \lt j, a[i] \gt a[j]} l_i + r_j$$$. Iterating over $$$j$$$, this is also doable using a segment tree.