E. POS Kiosk
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Odoo has introduced its new POS Kiosk app, which allows restaurants to receive orders from clients in their shop and process them easily. So basically, there are 2 main functionalities of the POS kiosk: add order , mark order as done so it's removed from the screen.

For performance reasons, the updates in the database are made in batches. It means that for each batch of updates, there is only one query executed to remove/add records to the database.

To test the database performance, Odoo developers came up with the following process :

  • There will be a randomly generated array of operations $$$A$$$ of size $$$n$$$ based on analytics of real data where $$$A_{i}$$$ is the difference between the created and deleted records of that batch of updates. For example, if $$$A_{i}=3$$$ , it means there are 3 more created records than deleted records in that batch of operations.
  • Now for every integers $$$L$$$ to $$$R$$$ $$$(1 \leq L \leq R \leq n)$$$ they will calculate $$$f(A,L,R)$$$ which goes as follows, from $$$L$$$ to $$$R$$$, executes the queries one by one, and reports the maximum extra units of space needed from its initial state if we consider that each record needs $$$1$$$ unit of space. It means that if $$$A_{i} \gt 0$$$ we need extra $$$A_{i}$$$ units of space to be able to execute that query , otherwise we free $$$-A_{i}$$$ units of space from the database that can be filled later by some other updates. For example, for the sequence $$$2$$$ $$$3$$$ $$$-4$$$ $$$6$$$, the answer is $$$7$$$, and for $$$2$$$ $$$3$$$ $$$-4$$$ $$$3$$$, the answer is $$$5$$$.

Given the generated array $$$A$$$, can you simulate the experiment and find : $$$$$$\sum_{1\leq L \leq R\leq n}f(A,L,R)$$$$$$

Input

The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 2 \cdot 10^{5})$$$, the number of testcases.

For each test case:

The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^{5})$$$, the size of the generated array of updates.

The second line contains $$$n$$$ integers $$$A_{i}$$$ $$$(-2 \cdot 10^3 \leq A_{i} \leq 2\cdot 10^{3})$$$, the data of the generated array.

The sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot 10^{5}$$$

Output

Print $$$T$$$ lines where the $$$i_{th}$$$ line contains the answer for the $$$i_{th}$$$ testcase.

Example
Input
2
3
-2 3 -5
7
1 -2 3 4 5 -10 223
Output
8
1672
Note

Explanation of the first test case:

  • for $$$[-2]$$$ the answer is $$$0$$$
  • for $$$[-2,3]$$$ the answer is $$$1$$$
  • for $$$[-2,3,-5]$$$ the answer is $$$1$$$
  • for $$$[3]$$$ the answer is $$$3$$$
  • for $$$[3,-5]$$$ the answer is $$$3$$$
  • for $$$[-5]$$$ the answer is $$$0$$$

The total sum is equal to $$$8$$$