Partition into increasing subsequences Specification

This challenge is simple to state: your input is a non-empty array of nonnegative integers, and your task is to partition it into as few increasing subsequences as possible.
More formally, if the input array is A, then the output is an array of arrays B such that:


Each arrays in B form a partition of A into disjoint (not necessarily contiguous) subsequences. Inductively, this means that either B is the singleton array containing A, or the first element of B is a subsequence of A and the rest form a partition of A with that subsequence removed.
Every array in B is (not necessarily strictly) increasing.
The number of arrays in B is minimal.


Both the input and output can be taken in the native array format of your language.
Note that there may be several correct outputs.

Example

Consider the input array A = [1,2,1,2,5,4,7,1].
One possible output is B = [[1],[1,2,4,7],[1,2,5]].
The partition condition is evident from this diagram:

A    1 2 1 2 5 4 7 1
B[0]               1
B[1] 1 2       4 7
B[2]     1 2 5


Also, each array in B is increasing.
Finally, A can't be split into two increasing subsequences, so the length of B is also minimal.
Thus it's a valid output.

Rules and scoring

You can write a function or a full program.
The lowest byte count wins, and standard loopholes are disallowed.
There is no time bound, but you should evauate your solution on all test cases before submitting it.

Test cases

Only one possible output is shown, but there may be several valid options.
In particular, the order of the arrays in the result doesn't matter (but each individual array should be in increasing order).

[0] -&gt; [[0]]
[3,5,8] -&gt; [[3,5,8]]
[2,2,2,2] -&gt; [[2,2,2,2]]
[1154,1012,976,845] -&gt; [[845],[976],[1012],[1154]]
[6,32,1,2,34,8] -&gt; [[1,2,8],[6,32,34]]
[1,12,1,12,1,13] -&gt; [[1,1,1,13],[12,12]]
[6,4,6,13,18,0,3] -&gt; [[0,3],[4,6,13,18],[6]]
[1,2,3,2,3,4,7,1] -&gt; [[1,1],[2,2,3,4,7],[3]]
[0,9,2,7,4,5,6,3,8] -&gt; [[0,2,3,8],[4,5,6],[7],[9]]
[7,1,17,15,17,2,15,1,6] -&gt; [[1,1,6],[2,15],[7,15,17],[17]]
[4,12,2,10,15,2,2,19,16,12] -&gt; [[2,2,2,12],[4,10,15,16],[12,19]]
[10,13,9,2,11,1,10,17,19,1] -&gt; [[1,1],[2,10,17,19],[9,11],[10,13]]
[3,7,3,8,14,16,19,15,16,2] -&gt; [[2],[3,3,8,14,15,16],[7,16,19]]
[15,5,13,13,15,9,4,2,2,17] -&gt; [[2,2,17],[4],[5,9],[13,13,15],[15]]
Haskell, 54 bytes

n#[]=[[n]]
n#(l:c)|[n]&lt;=l=(n:l):c|1&lt;2=l:n#c
foldr(#)[]


Usage example: foldr(#)[] [4,12,2,10,15,2,2,19,16,12]-> [[2,2,2,12],[4,10,15,16],[12,19]]

How it works: go through the input list starting at the right end. Build the output list (of lists) by prepending the current element n to first sublist l where n is less or equal to the head of l. If there's none, make a new singleton list of n at the end of the output list.