65 lines
1.5 KiB
Markdown
65 lines
1.5 KiB
Markdown
# B. Black Cells
|
||
|
||
[Codeforces](https://codeforces.com/contest/2026/problem/B)
|
||
|
||
You are given a strip divided into cells, numbered from left to right from 0 to 1018. Initially, all cells are white.
|
||
|
||
You can perform the following operation: choose two white cells `i` and `j`,
|
||
such that `i` ≠ `j` and |`i` − `j`| ≤ `k`, and paint them black.
|
||
|
||
A list `a` is given. All cells from this list must be painted black.
|
||
Additionally, at most one cell that is not in this list can also be painted black.
|
||
Your task is to determine the minimum value of `k` for which this is possible.
|
||
|
||
|
||
## Input
|
||
|
||
The first line contains a single integer `t` (1 ≤ `t` ≤ 500) — the number of test cases.
|
||
|
||
The first line of each test case contains a single integer `n` (1 ≤ `n` ≤ 2000).
|
||
|
||
The second line contains `n` integers `a1`, `a2`, ... , `an` (0 < `ai`< 1018; `ai` < `ai` + 1).
|
||
|
||
Additional constraint on the input: the sum of `n` across all test cases does not exceed 2000.
|
||
|
||
|
||
## Output
|
||
|
||
For each test case, print a single integer — the minimum value of `k`
|
||
for which it is possible to paint all the given cells black.
|
||
|
||
|
||
## Example
|
||
Input
|
||
|
||
```
|
||
4
|
||
2
|
||
1 2
|
||
1
|
||
7
|
||
3
|
||
2 4 9
|
||
5
|
||
1 5 8 10 13
|
||
```
|
||
|
||
Output
|
||
|
||
```
|
||
1
|
||
1
|
||
2
|
||
3
|
||
```
|
||
|
||
|
||
## Note
|
||
|
||
In the first example, with `k` = 1 , it is possible to paint the cells (1, 2).
|
||
|
||
In the second example, with `k` = 1, it is possible to paint the cells (7, 8).
|
||
|
||
In the third example, with `k` = 2, it is possible to paint the cells (2, 4) and (8, 9).
|
||
|
||
In the fourth example, with `k` = 3, it is possible to paint the cells (0, 1), (5, 8) and (10, 13).
|