To solve this problem, we will find the asymmetric value for each crop and compute the minimum asymmetric value for each crop's corresponding length. For every subtask, we find different ways to compute the asymmetric value of each crop.

Subtask 1

Considering iterating over all crops. A crop is defined by its left endpoint and right endpoint. Hence, we can use a nested for loop to first fix the left endpoint and then fix the right endpoint. There are other ways to loop through crops, such as looping through its left endpoint and its length and vice versa. To find the asymmetric value of a crop, we can have an accumulator and sum up the absolute difference for every such pair by looping over ~i~ defined in the problem statement. There are ~N \cdot (N-1)/2 = N^2/2 - N/2~ such crops, and we need about ~N~ calculations on average to compute the asymmetric value of each crop; hence, it runs in time that is roughly cubic in the number of mountains.

Subtask 2

For this subtask, we note that if we were to find the asymmetric value of each crop, then we have to do it faster than roughly ~N~ time. Now consider a crop with a left endpoint of ~l~ and a right endpoint of ~r~. We will take a closer look at the formula to compute the asymmetric value:

$$\displaystyle |h_l-h_r| + |h_{l+1}-h_{r-1}| + |h_{l+2}-h_{r-2}| + \dots + |h_{l+t}-h_{r-t}|$$

where ~t = \lfloor \frac{r-l}{2} \rfloor~. Note that because the array is non-decreasing in this subtask, then it follows that for mountains with indices ~i \le j~, we have that ~|h_i-h_j| = h_j-h_i~. Hence the above formula is equivalent to:

$$\displaystyle (h_r-h_l) + (h_{r-1}-h_{l+1}) + (h_{r-2}-h_{l+2}) + \dots + (h_{r-t}-h_{l+t}).$$

Let ~m = \frac{l+r}{2}~, which represents the midpoint of the mountains (it may not be an integer, but that does not matter). Notice that for every term whose index is greater than ~m~, it is being added, and for every term whose index is less than ~m~ it is being subtracted. We can then rearrange the formula to become:

$$\displaystyle h_r + h_{r-1} + h_{r-2} + \dots + h_{r-t} - (h_l + h_{l+1} + h_{l+2} + \dots + h_{l+t}).$$

Note that we have simplified this problem into static range sum queries. We can compute them quickly by building a prefix sum array of the mountains' heights (i.e., an array where the ~k~th element is the sum of the first ~k~ elements of ~h~) before iterating through all the crops. Note that to calculate the asymmetric crop, in this case, it will be constant time (i.e., independent of ~N~), so this runs in quadratic time in the number of mountains.

Subtask 3

We will now let ~[l, r]~ represent a crop where ~l \le r~ are the left and right endpoints, respectively. Now for this subtask, let us take a closer look at the formula for the crop ~[l, r]~:

$$\displaystyle |h_l-h_r| + (|h_{l+1}-h_{r-1}| + |h_{l+2}-h_{r-2}| + \dots + |h_{l+t}-h_{r-t}|).$$

Notice that the terms in brackets are the asymmetric value of the crop ~[l+1, r-1]~. If we have a way to iterate through the crops so that crop ~[l+1, r-1]~ comes right before ~[l, r]~, we can add ~|h_l-h_r|~ directly to the accumulator to get the asymmetric value of crop ~[l, r]~. This motivates us to cleverly iterate over the crops by fixing the midpoint and expanding outwards while maintaining an accumulator for each midpoint. Note that the midpoint will not be an actual mountain for crops with even length. This runs in time which is the square of the number of mountains. As we move from crop ~[l+1, r-1]~ to ~[l, r]~, we only add a term to the accumulator. Note that there exist dynamic programming solutions, but these were not necessary to receive full marks.