dp segment-tree partition https://codeforces.com/contest/2159/problem/D2
A very cool problem that relies on two clever observations
Main lesson: it’s always good to run/reason through a few test cases by hand and get a reasonable idea of what upper bounds are
Also, when you make an observation, simplify it!
- i.e. consider only suffix minimums ⇒ can assume array is strictly increasing