| Технокубок 2021 - Отборочный Раунд 1 |
|---|
| Закончено |
После боя с Шикамару Таюя решила, что ее флейта слишком предсказуемая, и поменяла ее на гитару. У гитары Таюи $$$6$$$ струн и бесконечное количество ладов, пронумерованных с $$$1$$$. Если зажать лад номер $$$j$$$ на $$$i$$$-й струне, то получится нота $$$a_{i} + j$$$.
Таюя хочет сыграть мелодию из $$$n$$$ нот. Ноты можно сыграть, используя различные комбинации струны и лада. Простота исполнения зависит от разности максимального и минимального номера используемых ладов. Чем эта величина меньше, тем проще исполнить технику. Требуется определить минимальную возможную разность.
Например, если $$$a = [1, 1, 2, 2, 3, 3]$$$, а последовательность нот — $$$4, 11, 11, 12, 12, 13, 13$$$ (что соответствует второму примеру), то можно сыграть первую ноту на первой струне, а все остальные ноты на шестой струне. Тогда максимальный лад будет $$$10$$$, минимальный $$$3$$$, и разница составит $$$10 - 3 = 7$$$, как показано на рисунке.
В первой строке через пробел заданы $$$6$$$ чисел $$$a_{1}$$$, $$$a_{2}$$$, ..., $$$a_{6}$$$ ($$$1 \leq a_{i} \leq 10^{9}$$$) — описания струн гитары Таюи.
Во второй строке задано число $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — количество нот, которое хочет сыграть Таюя.
В следующей строке через пробел заданы $$$n$$$ чисел $$$b_{1}$$$, $$$b_{2}$$$, ..., $$$b_{n}$$$ ($$$1 \leq b_{i} \leq 10^{9}$$$) — описание нот. Гарантируется, что $$$b_i > a_j$$$ для всех $$$1\leq i\leq n$$$ и $$$1\leq j\leq 6$$$. Иными словами, каждую ноту можно сыграть на любой струне.
Необходимо вывести минимальную возможную разность номеров используемых ладов.
1 4 100 10 30 5 6 101 104 105 110 130 200
0
1 1 2 2 3 3 7 13 4 11 12 11 13 12
7
В первом примере оптимальным будет сыграть первую ноту на первой струне, вторую ноту на второй струне, третью ноту на шестой струне, четвертую ноту на четвертой струне, пятую ноту на пятой струне, шестую ноту на третьей струне. Тогда для исполнения каждой ноты будет использоваться лад $$$100$$$, а разница составит $$$100 - 100 = 0$$$.
Во втором примере оптимальным будет, например, сыграть вторую ноту на первой струне, а все остальные ноты на шестой струне. Тогда максимальный лад будет $$$10$$$, минимальный $$$3$$$, и разница составит $$$10 - 3 = 7$$$.
