Line Trip
Contest: Educational Codeforces Round 158 (Rated for Div. 2)
Difficulty rating: 800
Tags: greedy, math

There is a road, which can be represented as a number line. You are located in the point $$$0$$$ of the number line, and you want to travel from the point $$$0$$$ to the point $$$x$$$, and back to the point $$$0$$$.

You travel by car, which spends $$$1$$$ liter of gasoline per $$$1$$$ unit of distance travelled. When you start at the point $$$0$$$, your car is fully fueled (its gas tank contains the maximum possible amount of fuel).

There are $$$n$$$ gas stations, located in points $$$a_1, a_2, \dots, a_n$$$. When you arrive at a gas station, you fully refuel your car. Note that you can refuel only at gas stations, and there are no gas stations in points $$$0$$$ and $$$x$$$.

You have to calculate the minimum possible volume of the gas tank in your car (in liters) that will allow you to travel from the point $$$0$$$ to the point $$$x$$$ and back to the point $$$0$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case consists of two lines:

- the first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 50$$$; $$$2 \le x \le 100$$$);
- the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 < a_1 < a_2 < \dots < a_n < x$$$).

Output format:
For each test case, print one integer — the minimum possible volume of the gas tank in your car that will allow you to travel from the point $$$0$$$ to the point $$$x$$$ and back.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case of the example, if the car has a gas tank of $$$4$$$ liters, you can travel to $$$x$$$ and back as follows:

- travel to the point $$$1$$$, then your car's gas tank contains $$$3$$$ liters of fuel;
- refuel at the point $$$1$$$, then your car's gas tank contains $$$4$$$ liters of fuel;
- travel to the point $$$2$$$, then your car's gas tank contains $$$3$$$ liters of fuel;
- refuel at the point $$$2$$$, then your car's gas tank contains $$$4$$$ liters of fuel;
- travel to the point $$$5$$$, then your car's gas tank contains $$$1$$$ liter of fuel;
- refuel at the point $$$5$$$, then your car's gas tank contains $$$4$$$ liters of fuel;
- travel to the point $$$7$$$, then your car's gas tank contains $$$2$$$ liters of fuel;
- travel to the point $$$5$$$, then your car's gas tank contains $$$0$$$ liters of fuel;
- refuel at the point $$$5$$$, then your car's gas tank contains $$$4$$$ liters of fuel;
- travel to the point $$$2$$$, then your car's gas tank contains $$$1$$$ liter of fuel;
- refuel at the point $$$2$$$, then your car's gas tank contains $$$4$$$ liters of fuel;
- travel to the point $$$1$$$, then your car's gas tank contains $$$3$$$ liters of fuel;
- refuel at the point $$$1$$$, then your car's gas tank contains $$$4$$$ liters of fuel;
- travel to the point $$$0$$$, then your car's gas tank contains $$$3$$$ liters of fuel.

Example input:
3
3 7
1 2 5
3 6
1 2 5
1 10
7

Example output:
4
3
7

Editorial:
We can iterate over the volume of the gas tank from $$$1$$$ to $$$\infty$$$ (in fact $$$200$$$ is enough due to problem limitations) and check whether it's enough to travel from the point $$$0$$$ to the point $$$x$$$, and back.
Let the volume be $$$V$$$, then all the following inequalities (which correspond to the ability to travel from the current gas station, having a full tank, to the next one) must be met: $$$a_1 - 0 \le V$$$, $$$a_2 - a_1 \le V$$$, ..., $$$a_n - a_{n-1} \le V$$$, and $$$2(x - a_n) \le V$$$ (the multiplier $$$2$$$ because there is no gas station at $$$x$$$, and we have to go from $$$a_n$$$ to $$$x$$$ and back without refueling). If all these conditions hold, then $$$V$$$ can be the answer.
However, we can notice that the minimum value of $$$V$$$ that is sufficient for the travel is just the maximum of the left sides of inequalities written above. In other words, the answer to the problem is $$$\max(a_1, a_2 - a_1, \dots, a_n - a_{n-1}, 2(x-a_n))$$$.