Для массива \(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\) удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.
Примечание
Пусть \(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\).