Скільки зростаючих - 2#5976
Нехай задано числову послідовність, що складається з цілих чисел.
Потрібно визначити кількість строго зростаючих підпослідовностей цієї послідовності.
У першому рядку вхідного файлу задано число . У наступному рядку через один або кілька пробілів наведено цілих чисел, які є членами заданої послідовності (1 \le N \le 100000, абсолютне значення членів послідовності не перевищує 1{,}25 \cdot 10^5).
В єдиному рядку виведіть відповідь на задачу. Відповідь потрібно подати за модулем (10^9+9).
Приклад 1