В большом интерактивном музее каждый зал имеет свой уровень сложности восприятия. Для исследовательской экскурсии нужно выбрать маршрут по залам так, чтобы уровни сложности на маршруте строго возрастали.

Маршрут задаётся как подпоследовательность исходного списка залов: можно пропускать некоторые залы, но нельзя менять их порядок.

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

Даны уровни сложности всех залов в порядке их расположения. Определите количество различных строго возрастающих подпоследовательностей максимальной длины.

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

В первой строке дано целое число n — количество залов.

Во второй строке дано n целых чисел a1, a2, ..., an, где ai — уровень сложности i-го зала.

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

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

Примечания

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

Ограничения

• 1 <= n <= 2000
• -10^6 <= ai <= 10^6

Пример 1

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

5
1 3 5 4 7

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

2

Пример 2

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

5
2 2 2 2 2

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

5

Пояснение к примерам

В первом примере максимальная длина строго возрастающей подпоследовательности равна 4. Таких подпоследовательностей две:

• 1, 3, 5, 7
• 1, 3, 4, 7

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