Minimum Ladders to Climb Buildings

You are given a sequence of buildings with specified heights. Starting from the first building, you must move sequentially to the last building. When moving from building i to building i+1, if the next building is taller than the current one (i.e. if arr[i] < arr[i+1]), you initially use a ladder to overcome the height difference.

However, you only have K ladders available. To optimize the usage, if at any point the number of ladder-assisted climbs exceeds K, you are allowed to “convert” one of the previously ladder-assisted climbs to a stair climb. Specifically, you always convert the climb with the largest height difference (i.e. the maximum jump) so that you can free up a ladder for other necessary climbs.

Your task is to determine the final number of ladder uses after optimally substituting some ladder climbs with stair climbs where possible.

Note: All height differences that require a ladder are processed in order. Whenever a new ladder is used and the total exceeds K, remove the largest jump from those previously recorded.

The mathematical formulation of a jump is given by: $$jump = arr[i+1] - arr[i]$$ whenever \(arr[i] < arr[i+1]\). If the total count of jumps exceeds \(K\), remove the maximum jump from the count.

inputFormat

The input is provided via standard input (stdin) and consists of three lines:

• The first line contains an integer \(N\) representing the number of buildings.
• The second line contains \(N\) space-separated integers, where the \(i\)-th integer is the height of the \(i\)-th building.
• The third line contains an integer \(K\) representing the maximum number of ladders available.

outputFormat

Output a single integer to standard output (stdout), which is the minimum number of ladders used after applying the optimization strategy.

5
1 5 2 6 4
2

2