Competitions
ISSPS`13 Wave 2 Day 5
Сколько возрастающих - 2
Пусть задана числовая последовательность, составленная из N целых чисел.
Определить количество строго возрастающих подпоследовательностей данной последовательности.
Input data
В первой строке входного файла дано число N, в следующей строке идут через один или несколько пробелов Nцелых чисел, члены заданной последовательности (1 ≤ N ≤ 100000, члены последовательности по модулю не превосходят 1,25·105).
Output data
В единственной строке – ответ задачи. Ответ выдать по модулю 1000000009 (109+9).
Examples
Input example #1
1 1
Output example #1
1