У Сережи есть последовательность, состоящая из 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
42
42
3
1 2 2
13
5
1 2 3 4 5
719
| Codeforces Round 187 (Div. 1) |
|---|
| Закончено |
