King Julian lined up n lemurs in front of him. The height of each lemur is an integer between 1 and n, and any two lemurs have different heights.

Julian wants to divide the line into several parts of non-intersecting subsegments, which, when combined, give the entire line. And then make sure that in each part the lemurs are arranged in ascending order of growth from left to right. If Julian decides to split the line into k pieces, he will have to pay the lemurs k * x shells.

After Julian breaks the line into parts, he can swap two lemurs, standing side by side in one part, an arbitrary number of times for one shell.

Find the minimum number of shells that Julian will need to get what he wants.

Input

The first line contains two integers n and x (1 ≤ n ≤ 300 000, 1 ≤ x ≤ 109) - the number of lemurs and the cost of one part.

The second line contains n different numbers hi (1 ≤ hi ≤ n) - the heights of the lemurs. It is guaranteed that all hi are distinct.

Output

Print a single number - the minimum number of shells that Julian will have to spend in order to achieve what he wants.