#P1319. Extreme Extension
Extreme Extension
题目描述
For an array of integers, the extreme value of this array is the minimum number of times (possibly, zero) the following operation has to be performed to make non-decreasing:
- Select an index such that , where is the current length of .
- Replace with two elements and such that and both are positive integers and .
- This way, the array changes and the next operation is performed on this modified array.
For example, if and index gets selected, then the possible arrays after this operation are , , or . 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 of integers. Help him find the sum of extreme values of all nonempty subarrays of modulo . If a subarray appears in multiple times, its extreme value should be counted the number of times it appears.
An array is a subarray of an array if can be obtained from 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 ( ) — the number of test cases.
The first line of each test case contains a single integer ( ).
The second line of each test case contains integers ( ).
It is guaranteed that the sum of over all test cases doesn't exceed .
输出格式
For each test case, print a single integer — the sum of extreme values of all subarrays of modulo .
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
提示
Let denote the extreme value of .
In the first test case,
- , because YouKn0wWho can perform the following operations on the subarray (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] $ ;
- , because $ [5, 4] \rightarrow [\underline{2}, \underline{3}, 4] $ ;
- , because $ [4, 3] \rightarrow [\underline{1}, \underline{3}, 3] $ ;
- , because they are already non-decreasing.
So the total sum of extreme values of all subarrays of .