You have an array (a) of length (n) consisting of non-zero integers. Initially, you have (0) coins, and you will do the following until (a) is empty: Let (m) be the current size of (a). Select an integer (i) where (1 \le i \le m), gain (|a_i|)(^{\text{∗}}) coins, and then: if (a_i < 0), then replace (a) with (a_1,a_2,\ldots,a_{i - 1}) (that is, delete the suffix beginning with (a_i)); otherwise, replace (a) with (a_{i + 1},a_{i + 2},\ldots,a_m) (that is, delete the prefix ending with (a_i)). if (a_i < 0), then replace (a) with (a_1,a_2,\ldots,a_{i - 1}) (that is, delete the suffix beginning with (a_i)); otherwise, replace (a) with (a_{i + 1},a_{i + 2},\ldots,a_m) (that is, delete the prefix ending with (a_i)). Find the maximum number of coins you can have at the end of the process. (^{\text{∗}})Here (|a_i|) represents the absolute value of (a_i): it equals (a_i) when (a_i > 0) and (-a_i) when (a_i < 0). The first line contains an integer (t) ((1 \le t \le 10^4)) — the number of testcases. The first line of each testcase contains an integer (n) ((1 \le n \le 2 \cdot 10^5)) — the length of (a). The second line of each testcase contains (n) integers (a_1,a_2,\ldots,a_n) ((-10^9 \le a_i \le 10^9), (a_i \ne 0)). The sum of (n) across all testcases does not exceed (2 \cdot 10^5). For each test case, output the maximum number of coins you can have at the end of the process. An example of how to get (23) coins in the first testcase is as follows: (a = 3, 1, 4, -1, -5, \color{red}{-9} \xrightarrow{i = 6} a = 3, 1, 4, -1, -5), and get (9) coins. (a = \color{red}{3}, 1, 4, -1, -5 \xrightarrow{i = 1} a = 1, 4, -1, -5), and get (3) coins. (a = \color{red}{1}, 4, -1, -5 \xrightarrow{i = 1} a = 4, -1, -5), and get (1) coin. $$$a = 4, -1, \color{red}{-5}