Задана послідовність цілих чисел. Знайдіть кількість її зростаючих підпослідовностей.

Вхідні дані

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

Вихідні дані

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