Extreme Extension

题意翻译

对于一个数列，定义一次操作为选择数列中任何一个元素 $a_i$ ，将这个位置替换成两个**正整数** $x,y$ 满足 $x+y=a_i$ 定义一个数列的极端值为将这个数列变成**不降**数列的最小操作次数 给定一个长度为 $n$ 的数列 $a$ （ $1\leq a_i\leq 10^5$ ），让你求它的所有非空子段的极端值之和，对 $\text{998244353}$ 取模 一个测试点中有多组数据，保证所有数据 $n$ 的规模总和不超过 $10^5$

题目描述

For an array $ b $ of $ n $ integers, the extreme value of this array is the minimum number of times (possibly, zero) the following operation has to be performed to make $ b $ non-decreasing: - Select an index $ i $ such that $ 1 \le i \le |b| $ , where $ |b| $ is the current length of $ b $ . - Replace $ b_i $ with two elements $ x $ and $ y $ such that $ x $ and $ y $ both are positive integers and $ x + y = b_i $ . - This way, the array $ b $ changes and the next operation is performed on this modified array. For example, if $ b = [2, 4, 3] $ and index $ 2 $ gets selected, then the possible arrays after this operation are $ [2, \underline{1}, \underline{3}, 3] $ , $ [2, \underline{2}, \underline{2}, 3] $ , or $ [2, \underline{3}, \underline{1}, 3] $ . And consequently, for this array, this single operation is enough to make it non-decreasing: $ [2, 4, 3] \rightarrow [2, \underline{2}, \underline{2}, 3] $ . It's easy to see that every array of positive integers can be made non-decreasing this way. YouKn0wWho has an array $ a $ of $ n $ integers. Help him find the sum of extreme values of all nonempty subarrays of $ a $ modulo $ 998\,244\,353 $ . If a subarray appears in $ a $ multiple times, its extreme value should be counted the number of times it appears. An array $ d $ is a subarray of an array $ c $ if $ d $ can be obtained from $ c $ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10\,000 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^5 $ ). It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 10^5 $ .

输出格式

For each test case, print a single integer — the sum of extreme values of all subarrays of $ a $ modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

4
3
5 4 3
4
3 2 1 4
1
69
8
7264 40515 28226 92776 35285 21709 75124 48163

输出样例 #1

5
9
0
117

说明

Let $ f(l, r) $ denote the extreme value of $ [a_l, a_{l+1}, \ldots, a_r] $ . In the first test case, - $ f(1, 3) = 3 $ , because YouKn0wWho can perform the following operations on the subarray $ [5, 4, 3] $ (the newly inserted elements are underlined): $ [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 $ , because $ [5, 4] \rightarrow [\underline{2}, \underline{3}, 4] $ ; - $ f(2, 3) = 1 $ , because $ [4, 3] \rightarrow [\underline{1}, \underline{3}, 3] $ ; - $ f(1, 1) = f(2, 2) = f(3, 3) = 0 $ , because they are already non-decreasing. So the total sum of extreme values of all subarrays of $ a = 3 + 1 + 1 + 0 + 0 + 0 = 5 $ .

题意翻译

对于一个数列，定义一次操作为选择数列中任何一个元素 $a_i$ ，将这个位置替换成两个**正整数** $x,y$ 满足 $x+y=a_i$ 定义一个数列的极端值为将这个数列变成**不降**数列的最小操作次数 给定一个长度为 $n$ 的数列 $a$ （ $1\leq a_i\leq 10^5$ ），让你求它的所有非空子段的极端值之和，对 $\text{998244353}$ 取模 一个测试点中有多组数据，保证所有数据 $n$ 的规模总和不超过 $10^5$