## Editorial for UTS Open '21 P6 - Terra Mater

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Aaeria

Binary search the minimum danger factor that requires or fewer operations to enforce.

Instead of finding the minimum number of hills that must be adjusted, find the maximum number of hills that can be left alone. The height difference between each consecutive hill is at most . So if hill and hill are both unadjusted, .

#### Partial Solution

Let the maximum number of unadjusted hills up to hill , assuming you don't adjust hill . Let be the last hill before that was unadjusted. for all . In total there can be unadjusted hills. This gives an solution, which doesn't give any points on DMOJ because this subtask doesn't exist.

#### Full Solution

The condition can be converted to , so you are trying to find the longest sequence of hills such that and . This is equivalent to finding the longest nondecreasing subsequence over pairs for which results in an solution.