Partition it into as few disjoint contiguous increasing subsequences as possible 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 substrings as possible, such that each substring is a permutation of a consecutive integer range.
More formally, if the input array is A, then the output is minimum number of partition of A into B(s):


Each arrays B form a partition of A into substrings. Inductively, this means that either B is the singleton array containing 1 element from A, or the elements of B is a subsequence of A, which when sorted are contiguous like x,x+1,x+2,...
The number of arrays B is minimal.


Example

Consider the input array A = [1,2,3,4,3,5].
Output is 2
One possible minimal partitions are B = [1,2,3],[4,3,5]. That's the only partition to 2 substrings.

{4,3,5} in sorted order is {3,4,5} which is contiguous.

Input

An array of integers A.

Output

A number, indicate the smallest number of parts A can be splitted to.

Winning criteria

Your submissions will be scored in bytes, with less bytes being better.
Kotlin, 91 bytes

fold(mutableListOf&lt;Int&gt;()){r,i-&gt;r.indexOfFirst{it&lt;i}.let{if(it&lt;0)r+=i else r[it]=i
r}}.size


Beautified

fold(mutableListOf&lt;Int&gt;()) {r,i-&gt;
    r.indexOfFirst { it&lt;i }.let {
        if (it&lt;0) r+=i else r[it]=i
        r
    }
}.size


Test

fun MutableList&lt;Int&gt;.f() =
fold(mutableListOf&lt;Int&gt;()){r,i-&gt;r.indexOfFirst{it&lt;i}.let{if(it&lt;0)r+=i else r[it]=i
r}}.size

fun main(args: Array&lt;String&gt;) {
    val i = mutableListOf(1,2,3,4,3,5)
    println(i.f())
}


TIO

TryItOnline