Dispatch Money
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a permutation $$$p_1, p_2, \ldots, p_n$$$.

You need to divide this permutation into disjoint non-empty segments (their total length should be equal to $$$n$$$), and for each of your chosen segments, you should pay $$$x$$$ coins.

After that, any number of times, you can spend one coin to swap two adjacent elements in one segment.

Find the minimum number of coins you should pay to divide this permutation into segments and make all segments sorted.

Input

The first line contains two integers $$$n,x$$$ ($$$1 \leq n \leq 300\,000, 1 \leq x \leq 10^9$$$).

The second line contains $$$n$$$ different integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$): the given permutation.

Output

Print one integer: the minimum number of coins that you should pay.

Examples

Input
5 1
5 4 3 2 1
Output
5
Input
1 1
1
Output
1
Input
10 10
9 10 8 3 7 5 6 2 1 4
Output
35