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: Set (b_{i+1} := b_{i+1} + b_i), Set (b_{i+1} := b_{i+1} - b_i). Set (b_{i+1} := b_{i+1} + b_i), 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 cha