In order to determine the length of such longest strictly increasing subsequence, we must, for each position ~X~ in the initial sequence, determine the length of the longest strictly increasing subsequence starting at a position to the right of ~X~ and ending at position ~X~ (the sequence is read from right to left), and the number of ways in which we can achieve that maximum. The same idea applies for the longest strictly decreasing subsequence. We can do this in a relatively simple fashion, using the Fenwick tree data structure in the time complexity of ~\mathcal O(N \log N)~.

We can notice that the solution is a union of a strictly increasing and a strictly decreasing subsequence such that the largest element of the strictly increasing subsequence is smaller than the smallest element of the strictly decreasing subsequence. If ~A~ is the length of the longest strictly increasing subsequence ending at position ~X~ (including position ~X~), and ~B~ the same for the strictly decreasing subsequence, and if ~num_A~, ~num_B~ are, respectively, the number of ways to obtain them, then the maximum length of the numbers to the right of ~X~ (including position ~X~) is ~A+B-1~, and the number of ways for getting this solution is ~num_A \times num_B~.

The required maximum length is the maximum of the described maximum lengths for each position. We denote this number with ~R~. Then the number of ways for which we can achieve this length is the product of the number of ways for all positions where the maximum length is equal to ~R~ multiplied with ~2^{N-R}~.

The factor ~2^{N-R}~ is necessary because, if a solution consists of ~R~ numbers, then each of the remaining ~N-R~ numbers could be placed independently before or after all numbers.

The time complexity of the solution is ~\mathcal O(N \log N)~.