CF2241G Summmon

Note that the answer for this problem might not fit in int64 or long long. It is recommended to use int128. For any array $ b $ of length $ m $ , define $ f(b) $ as the minimum possible value of $ \max(b) - \min(b) $ that can be achieved by performing the following operation any number of times: - Choose any index $ 1 \le i \lt m $ , and do exactly one of the following: 1. Set $ b_{i+1} := b_{i+1} + b_i $ , 2. Set $ b_{i+1} := b_{i+1} - b_i $ . You are given an array $ a $ of length $ n $ . Your task is to compute the sum of $ f $ over all the subarrays $ ^{\text{∗}} $ of $ a $ . More formally, determine the value of $$$ \sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r]). $$$ $ ^{\text{∗}} $ An array $ b $ is a subarray of an array $ a $ if $ b $ can be obtained from $ a $ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Description of each test case follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2\cdot10^5 $ ) — the length of the array $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

For each test case, print a single integer — the value of $ \sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r]) $ .

For the first test case, let us look at all subarrays. - For the single-element subarrays $ [6] $ , $ [4] $ , and $ [8] $ , no operation can change anything, so each of them contributes $ 0 $ . - For $ [6,4] $ , the first element is fixed as $ 6 $ . The second element can only be changed to $ 4+6=10 $ or $ 4-6=-2 $ , so the gap would become $ 4 $ or $ 8 $ . Hence, doing no operation is best, and the contribution is $ 2 $ . - For $ [4,8] $ , we choose $ i=1 $ and apply $ b_{2}:=b_{2}-b_{1} $ . Then the subarray becomes $ [4,4] $ , so its contribution is $ 0 $ . - For $ [6,4,8] $ , we keep the first two elements as they are and choose $ i=2 $ . Then we apply $ b_{3}:=b_{3}-b_{2} $ , so $ 8 $ becomes $ 4 $ . The array becomes $ [6,4,4] $ , and therefore $ \max(b)-\min(b)=6-4=2 $ . It can be shown that this is the optimal value. Therefore, the answer for the first test case is $ 0+0+0+2+0+2=4 $ . For the second test case, every subarray of length $ 1 $ contributes $ 0 $ . Among the remaining subarrays, only $ [2,3] $ , $ [3,4] $ , and $ [2,3,4] $ have a non-zero contribution, each contributing $ 1 $ . Therefore, the answer is $ 1+1+1=3 $ .