33OJ
登录 注册

#P17549. [JAG 2026 Summer Camp #2] Warp

[JAG 2026 Summer Camp #2] Warp

Problem Description

There is a circle with circumference LL, where LL is an even integer. Positions on the circle are measured counterclockwise and represented by real numbers in the range [0,L)[0,L).

There are NN points on this circle. The ii-th point is located at position AiA_i. The positions are not necessarily distinct.

Initially, you can choose any position on the circle as your starting position.

After that, you can move along the circle either clockwise or counterclockwise at a speed of 11 unit per second. You can change your direction at any time, without consuming any time.

Furthermore, you can use a magic warp at any time, as many times as you like. A magic warp takes no time and moves you to the exact opposite of your current position on the circle. More precisely, if you are at position xx (0≤x<L0\le x<L), a warp takes 00 seconds, and your position after the warp becomes

$$\begin{cases} x+L/2 & (0\le x<L/2),\\ x-L/2 & (L/2\le x<L). \end{cases}$$

A point is considered visited whenever your position coincides with its position. Find the minimum time, in seconds, required to visit all NN points at least once.

Input Format

The input consists of a single test case of the following format.

N L
A_1 A_2 ... A_N

The integer NN represents the number of points on the circle (1≤N≤2×1051\le N\le 2\times 10^5). The even integer LL represents the circumference of the circle (2≤L≤1092\le L\le 10^9). Each integer AiA_i satisfies 0≤Ai<L0\le A_i<L and indicates the location of the ii-th point on the circle (i=1,2,…,Ni=1,2,\ldots,N).

Output Format

Output the minimum time required to visit all NN points. It can be proved that the answer is an integer.

4 10
0 2 8 9
3
1 10
9
0
7 100
39 57 57 1 99 70 37
33

Hint

In Sample Input 1, it is possible to visit all 44 points in 33 seconds as follows.

  • First, you start at position 22, visiting the second point.
  • Move to position 33, taking 11 second.
  • Use a magic warp and move to position 88, taking 00 seconds. You also visit the third point.
  • Move to position 99, taking 11 second. You also visit the fourth point.
  • Move to position 00, taking 11 second. You also visit the first point.