От автора: возможно, некоторые из вас помнят задачу «Две мелодии» с Educational Codeforces Round 22. Пришло время сделать её немного сложнее!
Алиса — начинающий композитор, и недавно она записала два трека, ставшие очень популярными. Теперь у неё целая толпа фанатов, и все они ждут, когда Алиса запишет что-то ещё.
На этот раз для записи треков Алисе потребуются четыре мелодии.
У Алисы есть лист с n нотами на нем. Она хочет выбрать четыре такие непустые непересекающиеся подпоследовательности, что все они образуют мелодии и сумма их длин максимальна.
Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов.
Подпоследовательность образует мелодию, когда два соседних элемента либо отличаются на 1, либо сравнимы по модулю 7.
Напишите программу, которая найдет максимальную сумму длин четырёх таких непустых непересекающихся подпоследовательностей, что все они образуют мелодии.
Примечание
В первом примере можно составить 4 мелодии, взяв любые 4 ноты (по одной ноте в каждой мелодии).
Во втором примере есть одна мелодия длины 2 — {1, 2}. Остальные ноты используются в оставшихся трёх мелодиях (по одной ноте в мелодии).