Max Chunks to Make Sorted
mediumArrays & Prefix Sums+20 XPTime limit 2s
Split the array into consecutive chunks (every element in exactly one chunk). Then sort each chunk on its own and put the chunks back in their original order. You want the final array to be fully sorted in non-decreasing order.
What is the largest number of chunks you can use? (The array may contain repeated values.)
Input:
- line 1:
n - line 2:
nintegers
Output: the maximum number of chunks.
Constraints: 1 ≤ n ≤ 10⁵, −10⁹ ≤ a[i] ≤ 10⁹.
Think about it: you may cut after position i exactly when everything on the left is ≤ everything on the right — that is, max(a[0..i]) ≤ min(a[i+1..n−1]). Precompute suffix minimums, sweep a running prefix maximum, and count the valid cuts (plus the last chunk).
Sample input 1
5 2 1 3 4 4
Sample output 1
4
Sample input 2
5 5 4 3 2 1
Sample output 2
1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).