oops!

Don't read the previous version of this comment.

Solution: let's notice that if there are i, j such that i < j and a[i] >= a[j], then i and j belong to different SIS. Then, if there are such i, j, k such that i < j < k and a[i] >= a[j] >= a[k], all of them belong to different SIS, so there is no answer in this case. There is always an answer if there are no such i, j, k, because in this case: for every i, j such that i < j and a[i] >= a[j], every k from j + 1 to n will be such that a[k] > a[i] and a[k] > a[j], ==> we can add k to the SIS of i or j. So all you need to do is check if there is non-increasing subsequence of length more than 2. In this and only in this case there is no answer.

I think the problem 1144G - Слияние двух последовательностей is almost the same as yours.

Check this comment for a really good solution (but for a one increasing and a one decreasing subsequence):

Two merged subsequences greedy idea

You can adapt it easily to your situation with the following main modification:

If an element can be put in both arrays, but it in the array that has a larger last element (To give a chance for smaller elements to be put in the other array later).

We can do DP using the fact that the previous element must belong to increasing or decreasing subsequence. If we know to which it belongs, then we know whether we should minimize or maximize the last element of the other subsequence.

Go from left to right and store two variables: $$$smallest$$$ and $$$biggest$$$. When you are at position $$$i$$$, the variable $$$smallest$$$ is the smallest possible last element of the increasing subsequence, assuming that position $$$i-1$$$ was taken to the decreasing subsequence. And the same opposite thing for $$$biggest$$$ and assumption that $$$i-1$$$ is in the increasing subsequence.