Heaven's Kitchen 2

Season 1 aired last year, and Heaven's Kitchen season 2 airs this year. Every earlier season ran a tournament that all applicants entered, but the show became popular after season 1 and far too many cooks applied, so a tournament with everyone in it is no longer practical.

To bring the number of contestants down, the first match of this season takes only some of the applicants and splits them into two teams. The finalists chosen there go on to a tournament after the first match, which does not matter for this problem.

Many people join the first match at once, so the show grades cooking skill together with teamwork and with a performance that stands out in a large crowd. All of that is combined into a single integer for each cook, the star index. A negative value means the cook makes the show boring, and a positive value means the cook can shine on air. The larger the absolute value, the larger the influence.

The teams for the first match are formed like this.

1. Line up the $N$ cooks who applied to the program in a row.
2. Pick a group of one or more cooks who stand next to each other in the line. These cooks become team 1.
3. Pick one more group of one or more cooks who stand next to each other and do not overlap the first group. These cooks become team 2. Team 1 and team 2 do not have to be the same size.

The two teams do not have to be adjacent in the line, and a cook may belong to no team at all.

The combined performance of a team is the sum of the star indices of the cooks in that team. Two large performances keep the show entertaining, but a case bad enough that both performances are negative produces a memorable match of a different kind and raises the interest of the show. The interest of the show is therefore the product of the two combined performances.

The star indices of the $N$ cooks are already analyzed, and step 1, lining the cooks up, is already done. After steps 2 and 3 are carried out well, what is the interest of the most entertaining broadcast?

The first line contains the number of cooks $N$. ($2 \le N \le 10^5$)

The next line contains the star index $P_1, P_2, \dots, P_N$ of each cook, separated by spaces. ($-100 \le P_i \le 100$)

Print the largest interest the show can reach.