В текстовом файле записана последовательность, состоящая из n натуральных чисел. Петя собирает самую большую возрастающую подпоследовательность чисел, при этом ему нужно, чтобы все числа в этой подпоследовательности давали одинаковый остаток при делении на 4.
Пример: в последовательности 5 8 13 9 17 12 21 25 можно выбрать:
5 9 17 21 25 или 5 13 17 21 25 (остаток 1 при делении на 4, длина 5)8 12 (остаток 0 при делении на 4, длина 2)
Максимальная длина = 5.
Напишите программу, которая находит эту максимальную длину.
Формат входных данных
- В первой строке число n (1 ≤ n ≤ 20000)
- Во второй строке n чисел через пробел
Формат выходных данных
- Длина самой большой такой подпоследовательности
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
5 8 13 9 17 12 21 25
|
5
|