#P1603C. Extreme Extension
Extreme Extension
Description
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: .
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 .
Input
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 .
Output
For each test case, print a single integer — the sum of extreme values of all subarrays of modulo .
Note
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):
;
- , because ;
- , because ;
- , because they are already non-decreasing.
So the total sum of extreme values of all subarrays of .