Subtask 1

We imagine a line sweeping over the indices. Whenever ~A_i > A_{i-1}~, we need to add ~A_i - A_{i-1}~ new brush strokes starting at ~i~. We have the freedom to end brush strokes wherever we need to since we can use strokes of all lengths, so the final answer is just the sum of ~A_i - A_{i-1}~ where ~A_i > A_{i-1}~.

Time Complexity: ~\mathcal{O}(N)~

Subtask 2

This subtask was created to reward slower solutions with the correct idea presented below.

Time Complexity: ~\mathcal{O}(N^2)~

Subtask 3

First, let's solve a slightly modified version of the problem, where we have the extra constraint of ~R = N~. We can adopt the same approach from the first subtask, where we sweep over the indices from left to right. However, in this scenario, strokes do not become available for us to end immediately; instead, they must last at least ~L~ indices in length before we may end them. We can store how many strokes we may end in a new array ~B~, adding ~A_i - A_{i-1}~ to ~B_{i+L}~ whenever ~A_i > A_{i-1}~. If ~A_i < A_{i-1}~ and we do not have enough strokes that we are allowed to end, we simply evaluate the case as impossible.

Now, let's move back to the task at hand. The main observation to make is that any stroke with length greater than ~R~ can be composed by two shorter strokes with length in the range ~[L, R]~, the proof of which will be left as a simple exercise to the reader. This means that we can use the same approach as the modified version where ~R = N~, except the strokes longer than ~R~ cost us two strokes instead of one. To minimize the number of strokes that exceed length ~R~ in our solution, when necessary, we should always end the longest strokes available to us that have at most length ~R~. We can maintain the starting points of the brush strokes with a queue data structure as we sweep from left to right, removing indices from the queue and adjusting the answer appropriately when the stroke length exceeds ~R~.

Time Complexity: ~\mathcal{O}(N)~