Олимпиадный тренинг

Задача . C. Сережа и подпоследовательности


Задача

Темы: дп Структуры данных *2000

У Сережи есть последовательность, состоящая из n целых положительных чисел, a1, a2, ..., an.

Сначала Сережа записал на клетчатом листке бумаги все различные непустые неубывающие подпоследовательности последовательности a. Потом для каждой из последовательностей, записанных на клетчатом листке, Сережа записал на линованном листке все последовательности, которые ее не превышают.

Последовательность целых положительных чисел x = x1, x2, ..., xr не превышает последовательность целых положительных чисел y = y1, y2, ..., yr, если выполняются неравенства: x1 ≤ y1, x2 ≤ y2, ..., xr ≤ yr.

Сейчас Сережа интересуется, сколько последовательностей записано на листке в линию. Помогите Сереже, найдите остаток от деления описанного количества на 1000000007 (109 + 7).

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

В первой строке содержится целое число n (1 ≤ n ≤ 105). Во второй строке содержится n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 106).

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

В единственную строку выведите остаток от деления ответа на задачу на число 1000000007 (109 + 7).


Примеры
№Входные данныеВыходные данные
1 1
42 
42
2 3
1 2 2 
13
3 5
1 2 3 4 5 
719

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет