Max Chunks To Make Sorted II

Problem Split an array (duplicates allowed, values arbitrary) into the maximum number of contiguous chunks such that individually sorting each chunk and concatenating them yields the fully sorted array.

Input / Output

• Input: int array arr. Output: max chunk count.

Constraints

• n up to 10^5; O(n) expected.

Example

• [2,5,1,9,7,6] → 2 ([2,5,1] + [9,7,6]); [2,1,3,4,4] → 4 ([2,1],[3],[4],[4]).