Скільки зростаючих - 2

Нехай задано числову послідовність, що складається з N цілих чисел.

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

Вхідні дані

У першому рядку вхідного файлу задано число N. У наступному рядку через один або кілька пробілів наведено N цілих чисел, які є членами заданої послідовності (1 ≤ N ≤ 100000, абсолютне значення членів послідовності не перевищує 1,25·10^5).

Вихідні дані

В єдиному рядку виведіть відповідь на задачу. Відповідь потрібно подати за модулем 1000000009 (10^9+9).

Приклади