D. Две мелодии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса — начинающий композитор, и сейчас она собирается написать очередной шедевр. И даже не один, а сразу два!

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
4
1 2 4 5
Выходные данные
4
Входные данные
6
62 22 60 61 48 49
Выходные данные
5
Примечание

В первом примере подпоследовательности [1, 2] и [4, 5] дадут суммарную длину 4.

Во втором примере подпоследовательности [62, 48, 49] и [60, 61] дадут суммарную длину 5. Если выбрать первой подпоследовательностью [62, 61], то максимальная возможная длина второй мелодии будет 2, и результат будет 4, что не является максимальным ответом.