Задачі
Сколько возрастающих - 2
Сколько возрастающих - 2
Пусть задана числовая последовательность, составленная из \textbf{N} целых чисел.
Определить количество строго возрастающих подпоследовательностей данной последовательности.
\InputFile
В первой строке входного файла дано число \textbf{N}, в следующей строке идут через один или несколько пробелов \textbf{N} целых чисел, члены заданной последовательности (\textbf{1} ≤ \textbf{N} ≤ \textbf{100000}, члены последовательности по модулю не превосходят \textbf{1,25·10^5}).
\OutputFile
В единственной строке -- ответ задачи. Ответ выдать по модулю \textbf{1000000009} (\textbf{10^9+9}).
Вхідні дані #1
1 1
Вихідні дані #1
1