#P10961. [2015杭电多校]First One

    ID: 10103 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>CF1700普及+/提高-贡献法同向双指针一维前缀和等差数列求和

[2015杭电多校]First One

First One

Problem Description

soda has an integer array a1,a2,…,ana_1, a_2, \dots, a_n. Let S(i,j)S(i,j) be the sum of ai,ai+1,…,aja_i, a_{i+1}, \dots, a_j. Now soda wants to know the value below: $$\sum_{i=1}^{n} \sum_{j=i}^{n} (\lfloor \log_2 S(i,j) \rfloor + 1) \times (i + j)$$ Note: In this problem, you can consider log⁡20\log_2 0 as 0.

Input

There are multiple test cases. The first line of input contains an integer TT, indicating the number of test cases. For each test case: The first line contains an integer nn (1≤n≤105)(1 \le n \le 10^5), the number of integers in the array. The next line contains nn integers a1,a2,…,ana_1, a_2, \dots, a_n (0≤ai≤105)(0 \le a_i \le 10^5).

Output

For each test case, output the value.

Sample Input

1
2
1 1

Sample Output

12

Author

zimpha@zju

Source

2015 Multi-University Training Contest 6