Сколько возрастающих - 2

Пусть задана числовая последовательность, составленная из N целых чисел.

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

Входные данные

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

Выходные данные

В единственной строке – ответ задачи. Ответ выдать по модулю 1000000009 (10^9+9).

Примеры