给定一个长度为 $ n $ 的整数序列 $ a_1, a_2, \dots, a_n $，请找出一个**连续的非空子段**，使得该子段内所有整数之和最大。输出这个最大和。

本题要求使用**分治法**求解。

- 第一行包含一个整数 $ n （ 1 \le n \le 10^6 ）$，表示序列的长度。
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n ,（ |a_i| \le 10^9 ）$，表示序列中的元素。

输出一个整数，表示最大子段和。

### 样例说明

最大子段为 `1 7 5 -2 5`，其和为 $ 1+7+5-2+5 = 16 $。

## 数据范围与约定

- 对于 30% 的数据，$ n \le 100 $。
- 对于 100% 的数据，$ n \le 10^6 $。
- 序列元素绝对值不超过 $ 10^9 $。