2024-sp_Growing_Vegetables_is_Fun_5 (JOI JOI_spring)
Time limit: 5 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: order statistics, data structures, two pointers, binary search

![](_page_0_Picture_0.jpeg)

# Growing Vegetables is Fun 5

Bitaro, who has been enjoying gardening for many years, is planning to grow a plant called Bita-radish starting this spring.

Bitaro has prepared 2*N* Bita-radish seedlings. The seedlings are numbered from 1 to 2*N*, and Bitaro plans to arrange them in this order for cultivation. The size of seedling *i* (1 ≤ *i* ≤ 2*N*) is *Ai*. Bitaro wants every seedling to get enough sunlight, so the sizes of the seedlings satisfy the following conditions:

- *A*1 ≤ *A*2 ≤ · · · ≤ *AN* ≤ *AN*+1.
- *AN*+1 ≥ *AN*+2 ≥ · · · ≥ *A*2*N*-1 ≥ *A*2*N* ≥ *A*1.

Note that seedling 1 is the smallest and seedling *N* + 1 is the largest.

Bitaro has also prepared *N* red flowerpots and *N* blue flowerpots, each of which also has a certain size. The size of the *j*-th (1 ≤ *j* ≤ *N*) red flowerpot is *Bj*, and the size of the *k*-th (1 ≤ *k* ≤ *N*) blue flowerpot is *Ck*. Bitaro plants one Bita-radish seedling in each of these total 2*N* flowerpots, and arranges the flowerpots in a row so that seedlings 1, 2, . . . , 2*N* are in this order.

Considering the appearance, the 2*N* flowerpots must be arranged in a beautiful order. Here, a beautiful order means an arrangement of flowerpots such that there exist consecutive *N* flowerpots with the same color. More precisely, an arrangement of flowerpots is said to be a beautiful order if and only if there exists an integer *l* between 1 and *N* + 1 inclusive such that the colors of the flowerpots planted with seedlings *l*, *l*+1, . . . , *l*+*N* −1 are all the same.

When a seedling of size *y* is planted in a flowerpot of size *x*, the difficulty of cultivation for that pair is the absolute value |*x*−*y*|. Bitaro's workload in growing Bita-radish is the maximum difficulty of cultivation among the 2*N* pairs of flowerpots and seedlings.

Write a program which, given the information about the Bita-radish seedlings and flowerpots, finds the minimum possible value of Bitaro's workload when planting the seedlings so that the flowerpots are arranged in a beautiful order.

# Input

The input is given from Standard Input in the following format:

```
N
A1 A2 ... A2N
B1 B2 ... BN
C1 C2 ... CN
```

# Output

Print a single value - the minimum possible value of Bitaro's workload when planting the seedlings so that the flowerpots are arranged in a beautiful order - in a single line to Standard Output.

# Constraints

- 1 ≤ *N* ≤ 300000.
- 1 ≤ *Ai* ≤ 109 (1 ≤ *i* ≤ 2*N*).
- 1 ≤ *Bj* ≤ 109 (1 ≤ *j* ≤ *N*).
- 1 ≤ *Ck* ≤ 109 (1 ≤ *k* ≤ *N*).
- *A*1 ≤ *A*2 ≤ · · · ≤ *AN* ≤ *AN*+1.
- *AN*+1 ≥ *AN*+2 ≥ · · · ≥ *A*2*N*-1 ≥ *A*2*N* ≥ *A*1.
- All input values are integers.

### Subtasks

- 1. (4 points) *N* ≤ 5.
- 2. (5 points) *N* ≤ 10.
- 3. (21 points) *N* ≤ 2000.
- 4. (37 points) All values of *Ai* are distinct. Additionally, *AN* < *A*2*N* holds.
- 5. (33 points) No additional constraints.

### Sample Input and Output

| Sample Input 1 | Sample Output 1 |
|----------------|-----------------|
| 2              | 2               |
| 1 2 6 3        |                 |
| 2 5            |                 |
| 4 3            |                 |

In this sample input, Bitaro can achieve a workload of 2 by planting the seedlings as follows:

- Plant seedling 1 in the first red flowerpot. The difficulty of cultivation for this pair is |2 − 1| = 1.
- Plant seedling 2 in the second blue flowerpot. The difficulty of cultivation for this pair is |3 − 2| = 1.
- Plant seedling 3 in the first blue flowerpot. The difficulty of cultivation for this pair is |4 − 6| = 2.
- Plant seedling 4 in the second red flowerpot. The difficulty of cultivation for this pair is |5 − 3| = 2.

The colors of the flowerpots planted with seedlings 2 and 3 are both blue, so the flowerpots are arranged in a beautiful order.

It is impossible to achieve a workload less than 2 when planting the seedlings so that the flowerpots are arranged in a beautiful order. Therefore, the output is 2.

This sample input satisfies the constraints of all subtasks.

| Sample Input 2                               | Sample Output 2 |
|----------------------------------------------|-----------------|
| 9                                            | 8               |
| 1 2 3 4 5 6 7 8 9 18 17 16 15 14 13 12 11 10 |                 |
| 2 7 4 1 7 6 4 10 6                           |                 |
| 6 8 9 3 7 1 9 5 4                            |                 |

This sample input satisfies the constraints of subtasks 2, 3, 4 and 5.

| Sample Input 3                            | Sample Output 3 |
|-------------------------------------------|-----------------|
| 7                                         | 3               |
| 13 16 18 18 21 22 22 23 23 21 19 17 15 14 |                 |
| 14 14 20 19 22 17 25                      |                 |
| 24 15 18 25 24 19 11                      |                 |

This sample input satisfies the constraints of subtasks 2, 3 and 5.

Starter code:

Grader code:

Setup script:

Evaluation script: