#P17549. [JAG 2026 Summer Camp #2] Warp
[JAG 2026 Summer Camp #2] Warp
Problem Description
There is a circle with circumference , where is an even integer. Positions on the circle are measured counterclockwise and represented by real numbers in the range .
There are points on this circle. The -th point is located at position . 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 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 (), a warp takes 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 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 represents the number of points on the circle (). The even integer represents the circumference of the circle (). Each integer satisfies and indicates the location of the -th point on the circle ().
Output Format
Output the minimum time required to visit all 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 points in seconds as follows.
- First, you start at position , visiting the second point.
- Move to position , taking second.
- Use a magic warp and move to position , taking seconds. You also visit the third point.
- Move to position , taking second. You also visit the fourth point.
- Move to position , taking second. You also visit the first point.