题目描述

给定一个数字序列 $A_1, A_2, \ldots, A_n$，求 $i, j$（$1 \le i \le j \le n$），使得 $A_i + \cdots + A_j$ 最大，输出这个最大和。

输入格式

第一行输入一个整数 $n(n\leq 10^5)$，表示数列大小。