题目描述

有 $n$ 个整数排成一排，求其中的最大连续部分和。

至少要选一个数。

输入格式

第一行一个整数，表示 $n$。

第二行 $n$ 个整数 $x_1,x_2,\cdots,x_n$，相邻两数之间有一个空格。

输出格式

一个整数（即最大的连续的部分和）。

7
-2 13 12 9 14 -10 2

48

提示

本题相较于原题数据范围有所加强，略微卡常，请使用较快的输入输出方式。

$1\le n\le 10^7,0\le |x_i|\le 10^8$。