407637: GYM102862 A Two Subsequences

You are given a permutation $$$p$$$ of integers $$$1$$$ to $$$n$$$. You need to partition $$$p$$$ into two disjoint increasing subsequences such that the difference between the sizes of these subsequences is the maximum possible. Note that each element must belong to exactly one of the subsequences. The empty subsequence is also allowed.

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$), the number of elements in the permutation. The second line contains $$$n$$$ integers $$$p_i$$$ ($$$1 \leq p_i \leq n$$$), where the $$$i$$$-th of them equals the $$$i$$$-th element of the permutation. It is guaranteed that each integer from $$$\{1, \ldots, n\}$$$ appears exactly once among $$$p_i$$$.

Output a single integer, the maximum difference of sizes of subsequences. If it is not possible to partition the permutation into two disjoint increasing subsequences, output $$$-1$$$.

2
2 1

0

4
4 2 3 1

-1

10
2 4 5 1 6 3 7 8 9 10

6

11
1 2 3 4 5 6 7 8 9 10 11

11