You are given an array of size $N$. Your task is to replace any one element of the array with its corresponding square.

Find the maximum sum of subarrays after performing the task exactly once.

Input format

• First line: An integer $N$ denoting the size of the array
• Second line: $N$ space-separated integers denoting the elements of the array

Output format

• Print the maximum sum according to the problem statement.

Constraints
$1 \le N \le 5*10^5$

$-10^7 \le A[i] \le 10^7$