Алиса — начинающий композитор, и сейчас она собирается написать очередной шедевр. И даже не один, а сразу два!
У Алисы есть лист с n нотами на нем. Она хочет выбрать две такие непустые непересекающиеся подпоследовательности, что обе образуют мелодии и сумма их длин максимальна.
Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов.
Подпоследовательность образует мелодию, когда два соседних элемента либо отличаются на 1, либо сравнимы по модулю 7.
Напишите программу, которая найдет максимальную сумму длин двух таких непустых непересекающихся подпоследовательностей, что обе образуют мелодии.
Выходные данные
Выведите максимальную сумму длин двух таких непустых непересекающихся подпоследовательностей, что обе образуют мелодии.
Примечание
В первом примере подпоследовательности [1, 2] и [4, 5] дадут суммарную длину 4.
Во втором примере подпоследовательности [62, 48, 49] и [60, 61] дадут суммарную длину 5. Если выбрать первой подпоследовательностью [62, 61], то максимальная возможная длина второй мелодии будет 2, и результат будет 4, что не является максимальным ответом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 4 5
|
4
|
|
2
|
6
62 22 60 61 48 49
|
5
|