| Codeforces Round 346 (Div. 2) |
|---|
| Закончено |
Давным-давно Василий Иванович соорудил на своей даче хороший забор. Василий Иванович называет забор хорошим, если он представляет собой ряд из n последовательно скреплённых вертикальных досок сантиметровой ширины, высота каждой из которых — целое положительное число сантиметров. Хозяин дачи прекрасно помнит, что высота i-й слева доски равна hi.
Сегодня Василий Иванович решил изменить конструкцию сооружённого забора, спилив у него сверху связную часть таким образом, чтобы забор остался хорошим. Спиленная часть должна состоять только из верхних частей досок, причём соседние части должны быть соединены между собой (иметь ненулевую длину соприкосновения до выпиливания из забора).
Вам, как любопытному соседу Василия Ивановича, предстоит посчитать количество возможных способов спилить ровно одну часть, как описано выше. Два способа спилить часть называются различными, если для оставшихся заборов существует такое i, что высоты i-х досок различаются.
Поскольку забор Василия Ивановича может быть очень высоким и длинным, найдите остаток от деления искомого количества способов на 1 000 000 007 (109 + 7).
В первой строке содержится число n (1 ≤ n ≤ 1 000 000) — количество досок в заборе Василия Ивановича.
Во второй строке содержатся n разделённых пробелом чисел h1, h2, ..., hn (1 ≤ hi ≤ 109), где hi равно высоте i-й слева доски забора.
Выведите остаток при делении r на 1 000 000 007, где r — количество способов спилить ровно одну связную часть так, чтобы часть состояла из верхних частей досок и оставшийся забор был хорошим.
2
1 1
0
3
3 4 2
13
Из забора первого примера невозможно вырезать ровно одну часть таким образом, чтобы получившийся забор остался хорошим.
Все возможные варианты получившегося забора из второго примера выглядят следующим образом (серым цветом выделена вырезаемая часть):
