Multiselect

Time limit: 0.5s Memory limit: 4MB Input: Output:

William has recently been working on select algorithms! In case you’re not already familiar with them, these algorithms receive an array of length MM and an index KM1K \leq M - 1 in input. Then, through MM steps they rearrange the array contents, so that the KK-th element is in position KK of the array, with all smaller elements sitting on its left side, and all larger elements on its right side. No relative order, however, can be assumed between elements within a same side.

The select algorithm is ready, however, the problem William has to tackle requires a bit more work. He needs to process a very large array of length MM, so that at the end NN given different indexes K0K_0, \dots, KN1K_{N-1} are all partitioning the array.

Since William is lazy, he doesn’t want to write a new algorithm from scratch! Instead, he plans to re-use the select algorithm multiple times to achieve the desired effect. For example, assume that M=11M = 11, N=3N = 3 and the indexes KiK_i are 22, 44, 1010, as in Figure 22. One possible way to achieve the effect could be:

  • first, run select on the whole vector with K=4K = 4 (as in Figure 11), spending 1111 algorithm steps;
  • then, run select on the sub-vector [030 \dots 3] with K=2K = 2, which requires 44 algorithm steps;
  • finally, run select on the sub-vector [5105 \dots 10] with K=10K = 10, which requires 66 algorithm steps.

Overall, the procedure will require 1111 + 44 + 66 = 2121 algorithm steps. Notice that this is not the only possible way to obtain the result! Another could be:

  • run select on the whole vector with K=10K = 10, spending 1111 steps;
  • run select on the sub-vector [090 \dots 9] with K=2K = 2, spending 1010 steps;
  • run select on the sub-vector [292 \dots 9] with K=4K = 4, spending 88 steps.

With this other strategy, the procedure will require 1111 + 1010 + 88 = 2929 steps \dots not so good! Help William perform his task, minimising the number of algorithm steps required.

Input data

The first line contains the two integers NN and MM. The second line contains NN integers KiK_i.

Output data

You need to write a single line with an integer: the minimum total number of algorithm steps required to multi-select the given indexes from an array of length MM.

Constraints and clarifications

  • 1N1 0001 \leq N \leq 1 \ 000;
  • 1M1081 \leq M \leq 10^8;
  • 0K0<K1<<KN1<M0 \leq K_0 < K_1 < \dots < K_{N-1} < M;
# Score Constraints
1 0 Examples
2 19 N=MN = M
3 25 N5N \leq 5
4 40 N100N \leq 100
5 16 No additional limitations.

Example 1

stdin

3 11
2 4 10

stdout

21

Explanation

The first sample case is the one described in the problem statement.

Example 2

stdin

3 101
49 50 51

stdout

152

Explanation

In the second sample case, one way of achieving the lowest amount of steps is to first select K0K_0 = 4949 in 101101 steps, then K2K_2 = 5151 in further 5151 steps, getting K1K_1 = 5050 in place for free.

Log in or sign up to be able to send submissions!