[Solution] Rescheduling the Exam solution codeforces

Rescheduling the Exam solution codeforces – Now Dmitry has a session, and he has to pass 𝑛n exams. The session starts on day 11 and lasts 𝑑d days. The 𝑖ith exam will take place on the day of 𝑎𝑖ai (1𝑎𝑖𝑛1≤ai≤n), all 𝑎𝑖ai — are different. Orange — exam days. Before the first exam Dmitry will rest 22 days, before the second he will rest 11 day and before the third he will rest 33 days.

For the session schedule, Dmitry considers a special value 𝜇μ — the smallest of the rest times before the exam for all exams. For example, for the image above, 𝜇=1μ=1. In other words, for the schedule, he counts exactly 𝑛n numbers  — how many days he rests between the exam 𝑖1i−1 and 𝑖i (for 𝑖=0i=0 between the start of the session and the exam 𝑖i). Then it finds 𝜇μ — the minimum among these 𝑛n numbers.

Rescheduling the Exam solution codeforces

Dmitry believes that he can improve the schedule of the session. He may ask to change the date of one exam (change one arbitrary value of 𝑎𝑖ai). Help him change the date so that all 𝑎𝑖ai remain different, and the value of 𝜇μ is as large as possible.

For example, for the schedule above, it is most advantageous for Dmitry to move the second exam to the very end of the session. The new schedule will take the form:

Rescheduling the Exam solution codeforces
Dmitry can leave the proposed schedule unchanged (if there is no way to move one exam so that it will lead to an improvement in the situation).

Rescheduling the Exam solution codeforces

The first line of input data contains an integer 𝑡t (1𝑡1041≤t≤104) — the number of input test cases. The descriptions of test cases follow.

An empty line is written in the test before each case.

The first line of each test case contains two integers 𝑛n and 𝑑d (2𝑛2105,1𝑑1092≤n≤2⋅105,1≤d≤109) — the number of exams and the length of the session, respectively.

The second line of each test case contains 𝑛n integers 𝑎𝑖ai (1𝑎𝑖𝑑,𝑎𝑖<𝑎𝑖+11≤ai≤d,ai<ai+1), where the 𝑖i-th number means the date of the 𝑖i-th exam.

It is guaranteed that the sum of 𝑛n for all test cases does not exceed 21052⋅105.

Output

For each test case, output the maximum possible value of 𝜇μ if Dmitry can move any one exam to an arbitrary day. All values of 𝑎𝑖ai should remain distinct.

Rescheduling the Exam solution codeforces

9

3 12
3 5 9

2 5
1 5

2 100
1 2

5 15
3 6 9 12 15

3 1000000000
1 400000000 500000000

2 10
3 4

2 2
1 2

4 15
6 11 12 13

2 20
17 20

output

Copy
2
1
1
2
99999999
3
0
1
9

Rescheduling the Exam solution codeforces

The first sample is parsed in statement.

One of the optimal schedule changes for the second sample:

Initial schedule.

New schedule.

In the third sample, we need to move the exam from day 11 to any day from 44 to 100100.

In the fourth sample, any change in the schedule will only reduce 𝜇μ, so the schedule should be left as it is.

In the fifth sample, we need to move the exam from day 11 to any day from 100000000100000000 to 300000000300000000.

One of the optimal schedule changes for the sixth sample:

Initial schedule.

New schedule.

In the seventh sample, every day is exam day, and it is impossible to rearrange the schedule.

For Solution

Click Here

Leave a Comment