eolymp

Работа с забором

Фермер Фред хочет переделать забор в своем доме. Забор Фреда состоит n вертикальных деревянных досок разной высоты. Высота i-ой доски равна hi (1hin). Изначально все высоты различны.

Чтобы изменить конструкцию забора, Фред выбирает несколько смежных сегментов [l ... r] досок и “выравнивает“ их, разрезав так, чтобы все высоты были равны минимальной высоте на этом сегменте. Более конкретно, новые высоты сегмента становятся hi' = min{hl, hl+1, ..., hr} для всех lir.

Сколько различных конструкций может получить Фред, применив эту процедуру несколько (возможно, 0) раз? Поскольку ответ может быть большим, выведите его по модулю 109 + 7.

Две конструкции A и B отличаются, если есть доска, высота которой в A отличается от высоты в B.

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

Первая строка содержит количество досок n (1n3000) забора Фреда.

Вторая строка содержит n различных целых чисел hi (1hin, 1in) - высоты каждой из досок.

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

Выведите одно целое число - количество различных возможных конструкций забора, которое можно получить, по модулю 109 + 7.

Лимит времени 1 секунда
Лимит использования памяти 256 MiB
Входные данные #1
3
1 3 2
Выходные данные #1
4
Входные данные #2
5
1 2 3 4 5
Выходные данные #2
42
Входные данные #3
7
1 4 2 5 3 6 7
Выходные данные #3
124
Источник 2020 SEERC South Eastern European Regional Programming Contest, Винница и Бухарест, Май 23, Задача F