У Чанеки есть массив $$$[a_1,a_2,\ldots,a_n]$$$. Изначально все элементы покрашены в белый. Чанека выберет один или несколько различных индексов и покрасит элементы с этими индексами в черный цвет. Затем она выберет все белые элементы, чьи индексы кратны индексу по крайней мере одного черного элемента, и покрасит их в зеленый цвет. После этого ее оценка будет равна максимальному значению $$$a_i$$$ среди всех черных и зеленых элементов.
Существует $$$2^n-1$$$ способов выбрать черные индексы. Найдите сумму оценок для всех возможных способов, которыми Чанека может выбрать черные индексы. Поскольку ответ может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — размер массива $$$a$$$.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$0\leq a_i\leq10^5$$$).
Выведите одно целое число — сумму оценок по всем способам выбрать черные индексы по модулю $$$998\,244\,353$$$.
4 19 14 19 9
265
1 0
0
15 90000 9000 99000 900 90900 9900 99900 90 90090 9090 99090 990 90990 9990 99990
266012571
В первом примере ниже перечислены $$$15$$$ возможных вариантов выбора черных индексов:
Общая сумма составляет $$$19+14+19+9+19+19+19+19+14+19+19+19+19+19+19 = 265$$$.
Название |
---|