#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/11/problems/C

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Split Machine - Repovive Standard Round 4 | Repovive | Repovive

11C. Split Machine

1500 pts1s256 MB

You are given an array $a_1, a_2, \ldots, a_n$ .

A machine receives a non-empty array and returns a number. For an array of length $1$ , it returns $0$ .

For an array of length greater than $1$ , the machine chooses one of the boundaries between two consecutive elements and splits the array into two non-empty arrays $X$ and $Y$ .

Then the machine gets $f(X) + f(Y)$ , and adds exactly one of the following two values to it:

$sum(X) + sum(Y)$
$sum(X) \times sum(Y)$

Here $sum(Z)$ denotes the sum of all elements of array $Z$ .

The value $f(a)$ is the maximum possible final value over all choices of splits and added values.

For each test case, output $f(a)$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$1 \le a_i \le 10^4$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

1
5

Case 2

2
1 1

Case 3

3
1 2 1

Explanation

Case 1

The array has length $1$ , so the machine returns $0$ .

Case 2

There is only one split. The two sums are $1$ and $1$ , so the best added value is $1 + 1 = 2$ .

Case 3

An optimal splitting of the array is as follows: $\{1, 2\}$ and $\{1\}$ . Then we have: $f(\{1, 2\})+f(\{1\})+max((1+2) \times 1, (1+2) + 1)$ $=$ $3+0+4$ $=$ $7$ .

Output

Case 1

Case 2

Case 3

You are given an array $a_1, a_2, \ldots, a_n$ .

A machine receives a non-empty array and returns a number. For an array of length $1$ , it returns $0$ .

For an array of length greater than $1$ , the machine chooses one of the boundaries between two consecutive elements and splits the array into two non-empty arrays $X$ and $Y$ .

Then the machine gets $f(X) + f(Y)$ , and adds exactly one of the following two values to it:

$sum(X) + sum(Y)$
$sum(X) \times sum(Y)$

Here $sum(Z)$ denotes the sum of all elements of array $Z$ .

The value $f(a)$ is the maximum possible final value over all choices of splits and added values.

For each test case, output $f(a)$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$1 \le a_i \le 10^4$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

The array has length $1$ , so the machine returns $0$ .

There is only one split. The two sums are $1$ and $1$ , so the best added value is $1 + 1 = 2$ .

An optimal splitting of the array is as follows: $\{1, 2\}$ and $\{1\}$ . Then we have: $f(\{1, 2\})+f(\{1\})+max((1+2) \times 1, (1+2) + 1)$ $=$ $3+0+4$ $=$ $7$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

11C. Split Machine

Constraints

Input

Output

Samples

11C. Split Machine

Constraints

Input

Output

Samples