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

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

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

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

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