Задача №114031. Миллион алых роз
Восьмое марта только началось, а перед входом в цветочный магазин «Аделина» уже выстроилась огромная очередь желающих приобрести букеты красивейших свежих алых роз. Хозяин магазина Александр понимал, что день сегодня предстоит нелегкий. Поэтому он решил предварительно узнать у каждого из ожидающих покупателей, сколько всего роз тот хотел бы приобрести. Полученные числа Александр аккуратно выписал на листок и понял, что в одиночку ему не справиться.
Чтобы ускорить процесс формирования букетов, хозяин магазина позвал на помощь своего коллегу Михаила. Александр показал ему полученный только что список и предложил выписать подпоследовательность размеров букетов, формированием которых Михаил готов заняться.
Михаила не интересует оптимальное распределение работы. Не интересуют его также максимальный, минимальный и даже средний размеры формируемых им букетов. Все, что он хочет знать, — количество различных непустых подпоследовательностей в списке Александра по модулю 10 9 + 7 .
В первой строке вводится целое число N — количество ожидающих покупателей ( 1 ≤ N ≤ 1 000 000 ). Вторая строка содержит N натуральных чисел, i -е из которых описывает, сколько роз желает купить i -й человек в очереди ( 1 ≤ a i ≤ 1 000 000 ).
Выведите ответ на вопрос, терзающий Михаила, — количество различных подпоследовательностей в составленном Александром списке по модулю 1 000 000 007 ( 10 9 + 7 ).
Подпоследовательностью
называется числовая последовательность, которая составлена из членов последовательности
{
x
n
}
и в которой порядок следования ее элементов совпадает с их порядком следования в исходной последовательности
{
x
n
}
.
В тесте из условия Михаил может найти следующие 13 различных подпоследовательностей:
,
,
,
,
,
,
,
,
,
,
,
,
.
Тесты к этой задаче состоят из четырех групп.
- Тест 1. Тест из условия, оцениваемый в ноль баллов.
- Тесты 2–15. В тестах этой группы 1 ≤ a i ≤ N ≤ 15 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
- Тесты 16–31. В тестах этой группы 1 ≤ N ≤ 3 000 , 1 ≤ a i ≤ 10 5 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Тесты в этой группе оцениваются независимо.
Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.
4 1 2 1 3
13