Perform Easily
Contest: Technocup 2021 - Elimination Round 1
Difficulty rating: 1900
Tags: binary search, brute force, dp, implementation, sortings, two pointers

After battling Shikamaru, Tayuya decided that her flute is too predictable, and replaced it with a guitar. The guitar has $$$6$$$ strings and an infinite number of frets numbered from $$$1$$$. Fretting the fret number $$$j$$$ on the $$$i$$$-th string produces the note $$$a_{i} + j$$$.

Tayuya wants to play a melody of $$$n$$$ notes. Each note can be played on different string-fret combination. The easiness of performance depends on the difference between the maximal and the minimal indices of used frets. The less this difference is, the easier it is to perform the technique. Please determine the minimal possible difference.

For example, if $$$a = [1, 1, 2, 2, 3, 3]$$$, and the sequence of notes is $$$4, 11, 11, 12, 12, 13, 13$$$ (corresponding to the second example), we can play the first note on the first string, and all the other notes on the sixth string. Then the maximal fret will be $$$10$$$, the minimal one will be $$$3$$$, and the answer is $$$10 - 3 = 7$$$, as shown on the picture.

Input format:
The first line contains $$$6$$$ space-separated numbers $$$a_{1}$$$, $$$a_{2}$$$, ..., $$$a_{6}$$$ ($$$1 \leq a_{i} \leq 10^{9}$$$) which describe the Tayuya's strings.

The second line contains the only integer $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) standing for the number of notes in the melody.

The third line consists of $$$n$$$ integers $$$b_{1}$$$, $$$b_{2}$$$, ..., $$$b_{n}$$$ ($$$1 \leq b_{i} \leq 10^{9}$$$), separated by space. They describe the notes to be played. It's guaranteed that $$$b_i > a_j$$$ for all $$$1\leq i\leq n$$$ and $$$1\leq j\leq 6$$$, in other words, you can play each note on any string.

Output format:
Print the minimal possible difference of the maximal and the minimal indices of used frets.

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

Note:
In the first sample test it is optimal to play the first note on the first string, the second note on the second string, the third note on the sixth string, the fourth note on the fourth string, the fifth note on the fifth string, and the sixth note on the third string. In this case the $$$100$$$-th fret is used each time, so the difference is $$$100 - 100 = 0$$$.

In the second test it's optimal, for example, to play the second note on the first string, and all the other notes on the sixth string. Then the maximal fret will be $$$10$$$, the minimal one will be $$$3$$$, and the answer is $$$10 - 3 = 7$$$.

Example input:
1 4 100 10 30 5
6
101 104 105 110 130 200

Example output:
0

Example input:
1 1 2 2 3 3
7
13 4 11 12 11 13 12

Example output:
7

Editorial:
Consider all possible frets we may need to use. To do this we sort all the pairs $$$(b_j - a_i, j)$$$ lexicographically. Now we need to find a subsegment with the minimal range containing the first fields and also so that all numbers from $$$1$$$ to $$$n$$$ occur among the second fields (so it will mean that for each note there is at least one string-fret combination).
For each $$$l$$$, denote the minimal $$$right(l)$$$ so that $$$[l, right(l)]$$$ is a valid subsegment. It's easy to see that $$$right(l) \leq right(l + 1)$$$, because if $$$[l + 1, right(l + 1)]$$$ contains all numbers from $$$1$$$ to $$$n$$$ among the second fields, then so does $$$[l, right(l + 1)]$$$. So to find all $$$right(l)$$$ one can just use two pointers, maintaining the set of notes that occur on the segment.
Once we calculated it, we just print the minimal difference between the first fields of the endpoints of all possible segments $$$[l, right(l)]$$$. The final complexity is $$$O(nm\log(nm))$$$.