C. Экстремальное удлинение
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$b$$$ из $$$n$$$ целых чисел определим экстремальное значение этого массива как минимальное количество раз (возможно, нулевое), которое необходимо выполнить следующую операцию, чтобы массив $$$b$$$ стал неубывающим:

  • Выберите индекс $$$i$$$ такой, что $$$1 \le i \le |b|$$$, где $$$|b|$$$ — текущая длина $$$b$$$.
  • Замените $$$b_i$$$ двумя элементами $$$x$$$ и $$$y$$$ такими, что $$$x$$$ и $$$y$$$ являются целыми положительными числами и $$$x + y = b_i$$$.
  • Таким образом, массив $$$b$$$ изменяется, и следующая операция выполняется над этим измененным массивом.

Например, если $$$b = [2, 4, 3]$$$ и выбран индекс $$$2$$$, то возможными массивами после этой операции будут $$$[2, \underline{1}, \underline{3}, 3]$$$, $$$[2, \underline{2}, \underline{2}, 3]$$$, или $$$[2, \underline{3}, \underline{1}, 3]$$$. И, следовательно, для этого массива достаточно одной операции, чтобы он стал неубывающим: $$$[2, 4, 3] \rightarrow [2, \underline{2}, \underline{2}, 3]$$$.

Легко понять, что любой массив целых положительных чисел можно сделать неубывающим таким образом.

У YouKn0wWho есть массив $$$a$$$ из $$$n$$$ целых чисел. Помогите ему найти сумму экстремальных значений по всем непустым подмассивам массива $$$a$$$ по модулю $$$998\,244\,353$$$. Если некоторый подмассив встречается в $$$a$$$ несколько раз, его экстремальное значение нужно учесть столько раз, сколько он встречается.

Массив $$$d$$$ является подмассивом массива $$$c$$$, если $$$d$$$ может быть получен из $$$c$$$ удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число  — сумму экстремальных значений по всем подмассивам $$$a$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
3
5 4 3
4
3 2 1 4
1
69
8
7264 40515 28226 92776 35285 21709 75124 48163
Выходные данные
5
9
0
117
Примечание

Пусть $$$f(l, r)$$$ обозначает экстремальное значение в подмассиве $$$[a_l, a_{l+1}, \ldots, a_r]$$$.

В первом наборе входных данных:

  • $$$f(1, 3) = 3$$$, потому что YouKn0wWho может выполнить следующие операции над подмассивом $$$[5, 4, 3]$$$ (новые вставленные элементы подчеркнуты):

    $$$[5, 4, 3] \rightarrow [\underline{3}, \underline{2}, 4, 3] \rightarrow [3, 2, \underline{2}, \underline{2}, 3] \rightarrow [\underline{1}, \underline{2}, 2, 2, 2, 3]$$$;

  • $$$f(1, 2) = 1$$$, потому что $$$[5, 4] \rightarrow [\underline{2}, \underline{3}, 4]$$$;
  • $$$f(2, 3) = 1$$$, потому что $$$[4, 3] \rightarrow [\underline{1}, \underline{3}, 3]$$$;
  • $$$f(1, 1) = f(2, 2) = f(3, 3) = 0$$$, потому что они уже неубывающие.

Таким образом, общая сумма экстремальных значений всех подмассивов $$$a = 3 + 1 + 1 + 0 + 0 + 0 = 5$$$.