Задача №111777. Число возрастающих подпоследовательностей
Задана последовательность из n чисел a1, a2, ..., an. Подпоследовательностью длины k этой последовательности называется набор индексов i1, i2, ..., ik, удовлетворяющий неравенствам 1 ≤ i1 < i2 < ... < ik ≤ n. Подпоследовательность называется возрастающей, если выполняются неравенства ai1 < ai2 < ... < aik.
Необходимо найти число возрастающих подпоследовательностей наибольшей длины заданной последовательности a1, ... ,an. Так как это число может быть достаточно большим, необходимо найти остаток от его деления на 109 + 7.
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 105). Вторая строка входного файла содержит n целых чисел: a1, a2, ... ,an. Все ai не превосходят 109 по абсолютной величине.
В выходной файл выведите ответ на задачу.
5 1 2 3 4 5
1
6 1 1 2 2 3 3
8