B. Эффект от крема против прыщей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Чанеки есть массив $$$[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$$$ возможных вариантов выбора черных индексов:

  • Индекс $$$1$$$ - черный. Индексы $$$2$$$, $$$3$$$ и $$$4$$$ - зеленые. Максимальное значение среди них - $$$19$$$.
  • Индекс $$$2$$$ - черный. Индекс $$$4$$$ - зеленый. Максимальное значение среди них - $$$14$$$.
  • Индекс $$$3$$$ - черный. Максимальное значение среди них - $$$19$$$.
  • Индекс $$$4$$$ - черный. Максимальное значение среди них - $$$9$$$.
  • Индексы $$$1$$$ и $$$2$$$ - черные. Индексы $$$3$$$ и $$$4$$$ - зеленые. Максимальное значение среди них - $$$19$$$.
  • Индексы $$$1$$$ и $$$3$$$ - черные. Индексы $$$2$$$ и $$$4$$$ - зеленые. Максимальное значение среди них - $$$19$$$.
  • Индексы $$$1$$$ и $$$4$$$ - черные. Индексы $$$2$$$ и $$$3$$$ - зеленые. Максимальное значение среди них - $$$19$$$.
  • Индексы $$$2$$$ и $$$3$$$ - черные. Индекс $$$4$$$ - зеленый. Максимальное значение среди них - $$$19$$$.
  • Индексы $$$2$$$ и $$$4$$$ - черные. Максимальное значение среди них - $$$14$$$.
  • Индексы $$$3$$$ и $$$4$$$ - черные. Максимальное значение среди них - $$$19$$$.
  • Индексы $$$1$$$, $$$2$$$ и $$$3$$$ - черные. Индекс $$$4$$$ - зеленый. Максимальное значение среди них - $$$19$$$.
  • Индексы $$$1$$$, $$$2$$$ и $$$4$$$ - черные. Индекс $$$3$$$ - зеленый. Максимальное значение среди них - $$$19$$$.
  • Индексы $$$1$$$, $$$3$$$ и $$$4$$$ - черные. Индекс $$$2$$$ - зеленый. Максимальное значение среди них - $$$19$$$.
  • Индексы $$$2$$$, $$$3$$$ и $$$4$$$ - черные. Максимальное значение среди них - $$$19$$$.
  • Индексы $$$1$$$, $$$2$$$, $$$3$$$ и $$$4$$$ - черные. Максимальное значение среди них - $$$19$$$.

Общая сумма составляет $$$19+14+19+9+19+19+19+19+14+19+19+19+19+19+19 = 265$$$.