Lemurs rearrangement#11124
King Julian lined up lemurs in a row. The height of each lemur is an integer between and , and all heights are distinct.
Julian wants to divide the row into several non-overlapping subsegments such that their union covers the entire row. In each subsegment, the lemurs must be arranged in order of increasing height from left to right. If Julian splits the row into subsegments, he will have to pay the lemurs shells.
After dividing the row, Julian can swap two adjacent lemurs within any one subsegment any number of times, for one shell per swap.
Find the minimum number of shells that Julian needs to spend to achieve his goal.
The first line contains two integers and (1 \le n \le 300\,000, 1 \le x \le 10^9) — the number of lemurs and the cost of creating one subsegment.
The second line contains distinct integers h_1, h_2, \ldots, h_n (1 \le h_i \le n) — the heights of the lemurs.
Print a single integer — the minimum number of shells that Julian must spend to achieve his goal.
Example 1
Example 2
Example 3