После боя с Шикамару Таюя решила, что ее флейта слишком предсказуемая, и поменяла ее на гитару. У гитары Таюи \(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\), как показано на рисунке.
Выходные данные
Необходимо вывести минимальную возможную разность номеров используемых ладов.
Примечание
В первом примере оптимальным будет сыграть первую ноту на первой струне, вторую ноту на второй струне, третью ноту на шестой струне, четвертую ноту на четвертой струне, пятую ноту на пятой струне, шестую ноту на третьей струне. Тогда для исполнения каждой ноты будет использоваться лад \(100\), а разница составит \(100 - 100 = 0\).
Во втором примере оптимальным будет, например, сыграть вторую ноту на первой струне, а все остальные ноты на шестой струне. Тогда максимальный лад будет \(10\), минимальный \(3\), и разница составит \(10 - 3 = 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 4 100 10 30 5
6
101 104 105 110 130 200
|
0
|
|
2
|
1 1 2 2 3 3
7
13 4 11 12 11 13 12
|
7
|