G. Четыре мелодии
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

От автора: возможно, некоторые из вас помнят задачу «Две мелодии» с Educational Codeforces Round 22. Пришло время сделать её немного сложнее!

Алиса — начинающий композитор, и недавно она записала два трека, ставшие очень популярными. Теперь у неё целая толпа фанатов, и все они ждут, когда Алиса запишет что-то ещё.

На этот раз для записи треков Алисе потребуются четыре мелодии.

У Алисы есть лист с n нотами на нем. Она хочет выбрать четыре такие непустые непересекающиеся подпоследовательности, что все они образуют мелодии и сумма их длин максимальна.

Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов.

Подпоследовательность образует мелодию, когда два соседних элемента либо отличаются на 1, либо сравнимы по модулю 7.

Напишите программу, которая найдет максимальную сумму длин четырёх таких непустых непересекающихся подпоследовательностей, что все они образуют мелодии.

Входные данные

В первой строке записано одно целое число n (4 ≤ n ≤ 3000).

Во второй строке записано n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 105) — ноты на листе.

Выходные данные

Выведите максимальную сумму длин четырёх таких непустых непересекающихся подпоследовательностей, что все они образуют мелодии.

Примеры
Входные данные
5
1 3 5 7 9
Выходные данные
4
Входные данные
5
1 3 5 7 2
Выходные данные
5
Примечание

В первом примере можно составить 4 мелодии, взяв любые 4 ноты (по одной ноте в каждой мелодии).

Во втором примере есть одна мелодия длины 2 — {1, 2}. Остальные ноты используются в оставшихся трёх мелодиях (по одной ноте в мелодии).