$A_i \times A_j$

Interview

Time limit1sMemory limit1024 MB

Summary

Given an array, pick two different elements, replace both with their product, and find the maximum array sum possible with at most one such operation.

Level: Medium5 of 10
Topics: Array, Sorting, Greedy, Math
Solved: No attempts yet

Problem

You are given an array of size $N$ . You may apply the following operation at most once.

Choose two elements $A_i$ and $A_j$ from the array. ( $i \neq j$ )
Replace both chosen elements with $A_i \times A_j$ .

Find the maximum possible sum of the array after applying the operation at most once.

Input

The first line contains the size of the array $N$ . ( $2 \leq N \leq 2 \times 10^5$ )

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ , separated by spaces. ( $-10^9 \leq A_i \leq 10^9$ )

Output

Print the maximum possible sum of the array.

Examples2

Example 1
Input
```
4
3 -2 4 7
```
Expected output
```
57
```
Example 2
Input
```
2
1 0
```
Expected output
```
1
```