Дерево Фенвика

Дерево Фенвика − это структура данных, эффективно поддерживающая запросы о сумме префикса числового массива. Для числа t обозначим h(t) максимальное значение k, такое что t делится на 2k. Например, h(24)=3, h(5)=0. Обозначим l(t)=2h(t), например, l(24)=8, l(5)=1.

Рассмотрим массив a[1], a[2], … , a[n] целых чисел. Дерево Фенвика для этого массива — это массив b[1], b[2], …, b[n], такой что  \( \sum\limits_{j=i-l(i)+1}^{i}a[j] \) Таким образом: b[1]=a[l], b[2]=a[l]+a[2], b[3]=a[3], b[4]=a[l]+a[2]+a[3]+a[4], b[5]=a[5], b[6]=a[5]+a[6], Например, дерево Фенвика для массива a=(3,−1,4,1,−5,9) есть массив b=(3,2,4,7,−5,4).

Назовем массив само-фенвиковским, если он совпадает со своим деровом Фенвика. Напрмер, массив a=(0,−1,1,1,0,9) таковым является.

Вам дан массив а. Вам разрешается заменять в нем некоторые элементы, не меняя их порядка, чтобы сделать из исходного массива само-фенвиковский. Количество изменений при этом должно быть минимально возможным.

Входные данные
В первой строке входных данных содержится количество чисел в массиве n (1 ≤ n ≤ 100000). Во второй строке находятся сами n целых чисел. Все числа по модулю не превосходят 10⁹.

Выходные данные
Выведите n чисел − элементы видоизмененного массива. Если решений несколько − выведите любое из них.

Назовем подпоследовательностью массива a непустой массив b такой, что он может быть получен из массива a удалением нескольких (возможно, никаких) элементов массива a. Например, массив [1,3]  является попоследовательностью массива [1,2,3] , но [3,1]  не является.

Назовем подотрезком массива a непустой массив b такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива a. Например, [1,2]  является подотрезком массива [1,2,3] , а [1,3]  не является. Несложно заметить, что у массива длины n ровно  \( {n(n+1) \over 2}\)  подотрезков.

Назовем массив a длины n возрастающим , если для любого 1 ≤ i ≤ n выполняется a_i ≤ a_i+1.

Монотонностью массива назовем количество его возрастающих подотрезков.

Дан массив a длины n. Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю 10⁹+7.

Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 200000) — длина массива a.
Во второй строке заданы n целых чисел (1 ≤ a_i ≤ 200000) — элементы массива a.

Выходные данные
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю 10⁹+7.

Примечание
В первом тестовом примере у массива есть 7 подпоследовательностей:

• У массива [1]  есть ровно один подотрезок и он является возрастающим.
• У массива [2]  есть ровно один подотрезок и он является возрастающим.
• У массива [3]  есть ровно один подотрезок и он является возрастающим.
• У массива [1,2]  есть три подотрезка ([1], [2], [1,2] ) и все они являются возрастающими.
• У массива [1,3]  есть три подотрезка ([1], [3], [1,3] ) и все они являются возрастающими.
• У массива [3,2]  есть три подотрезка ([3], [2], [3, 2] ), но только два из них ([3]  и [2] ) являются возрастающими.
• У массива [1,3,2]  есть шесть подотрезков ([1], [3], [2], [1,3], [3,2], [1,3,2] ) и четыре из них ([1], [3], [2], [1,3] ) являются возрастающими.

Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину 1.

Примеры

№	Входные данные	Выходные данные
1	3 1 3 2	15
2	3 6 6 6	12