最大区间和
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为 n 的数组 a_1, a_2, \dots, a_n，其中每个元素 a_i 都属于 {-1, 0, 1}。定义区间 [l, r] 的得分为
f(l, r) = \left(\sum_{i=l}^{r} a_i\right) \times (r - l + 1).


同时定义前缀和 p[j] = \sum_{i=1}^{j} a_i ，并且满足对于所有 j 都有 |p[j]| \le 5000。

你的任务是求出所有区间 [l, r] 中 f(l, r) 的最大值。
不能取空区间

输入描述:

- 第一行包含一个整数 n(1\le n\le 10^6)。
- 第二行包含 n 个整数 a_1, a_2, \dots, a_n，每个 a_i \in \{-1, 0, 1\}。

输出描述:

输出一个整数，表示最大的 f(l, r) 值。
示例1

输入

复制 
5
1 -1 1 0 1

输出

复制 
10

说明

[1,n] 时最大