Orchard Row Yield After One Graft

An orchard keeper tends a single row of N fruit trees, numbered 1 to N. Tree i currently produces a yield of a_i units per season — this can be negative, meaning the tree is diseased and actually costs that many units to maintain.

This season the keeper must graft exactly one tree in the row (any single tree of their choosing — this step cannot be skipped, and no more than one tree may be grafted). Grafting a tree replaces its yield with the square of its current yield, i.e. tree i's yield becomes a_i * a_i. Every other tree's yield stays exactly as it was.

After the graft, the keeper selects one contiguous, non-empty stretch of trees to harvest and collects the sum of the yields of exactly those trees. The keeper chooses both which tree to graft and which stretch to harvest, in order to maximize the total harvested yield. What is the largest total the keeper can obtain?

Input format

The first line contains a single integer N. The second line contains N integers a_1, a_2, ..., a_N.

Output format

Print a single integer: the maximum total harvested yield achievable after grafting exactly one tree.

Constraints

• 1 ≤ N ≤ 20,000
• -10,000 ≤ a_i ≤ 10,000

4
2 -3 4 1

17

6
3 -4 2 -7 1 5

57