Towers#11825
In a distant country, there are watchtowers with heights described by the sequence h = (h_1, h_2, \dots, h_n). The authorities have decided to undergo reconstruction to ensure reliable observation between two key towers: the first (h_1) and the last (h_n).
To ensure proper visibility, at least other towers (that is, with numbers from to n-1) must fall within the "visibility zone". A tower falls within the visibility zone if its height is within the line of sight between the first and last towers, i.e., it is not lower than the lower of the two and not higher than the higher of the two.
Formally, let l = \min(h_1, h_n), r = \max(h_1, h_n). Tower (2 \le i \le n-1) falls within the zone if l \le h_i \le r.
You can reconstruct the towers by changing their heights. In one operation, you can increase or decrease the height of any tower by .
Find the minimum number of such operations needed to ensure that at least towers (from to n-1) fall within the visibility zone between the first and last.
The first line contains two integers and (3 \le n \le 2 \cdot 10^5, 1 \le m \le n - 2) — the total number of towers and the minimum number that must fall within the visibility zone.
The second line contains integers h_1, h_2, \dots, h_n (1 \le h_i \le 10^9) — the initial heights of the towers.
Output one number — the minimum number of operations needed to achieve the goal.
Example 1
Example 2