eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Возрастающая подпоследовательность

Возрастающая подпоследовательность

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Задана последовательность целых чисел. Найдите количество её возрастающих подпоследовательностей.

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

Первая строка содержит длину последовательности n (1n500), а вторая - её элементы (натуральные числа, меньшие 5000).

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

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

Пример

Входные данные #1
3
1 2 3
Выходные данные #1
7
Входные данные #2
3
3 1 2
Выходные данные #2
4