Split Machine - Repovive Standard Round 4 | 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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

11C. Split Machine

Constraints

Input

Output

Samples

11C. Split Machine

Constraints

Input

Output

Samples