Юному Шелдону очень интересно проводить эксперименты, результатом которых являются различные последовательности чисел. После проведения очередных экспериментов, Шелдон получил определенную последовательность чисел и заинтересовался вопросом, сможет ли он из исходной последовательности вычеркнуть некоторые числа таким образом, чтобы оставшиеся числа образовывали возрастающую подпоследовательность, где каждый элемент строго больше предыдущего. Шелдон хочет вычеркнуть как можно меньше чисел (в том числе, если можно, то ничего не вычеркивать).
Теперь он хочет узнать, сколько существует различных вариантов выбрать одну такую подпоследовательность из данной последовательности чисел. Помогите юному Шелдону найти ответ для заданной последовательности чисел.
Входные данные
Первая строка содержит натуральное число
n - длина последовательности Шелдона. Вторая строка содержит
n чисел - элементы последовательности (
numsi).
Ограничения
1 <= n <= 2000-106 <= numsi <= 106
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
1 3 5 4 7
|
2
|
2
|
5
2 2 2 2 2
|
5
|