T101688 [III] Gold Experience Requiem

$$\text{「所謂的覺悟 ..不是抱定犧牲的決心 ,」}$$ $$\text{「而是 —— 在黑暗的荒野中 ... 劈出前進的道路\ !!!」}$$

给你一个长度为 $N$ 的数列 $num\{\}(-10^2 \leq num_i \leq 10^2)$。 要求你在这个数列 $num\{\}$ 的所有连续子序列 $X\{\}$ 中找到一个和 (和记作 $K$) 最大的连续子序列 $A\{\}$。 要求输出全部可能的 $K$ 的和。 因为替身能量过于强大，所以要求将答案 $\bmod\ 10^5$。 --- 即，求 $$\sum\limits_{i=1}^N\sum\limits_{j=i}^N\max\limits_{x=i}^j\max\limits_{y=x}^j\sum\limits_{k=x}^y num_k \pmod{10^5}$$

第一行两个正整数 $N$。 第二行 $N$ 个正整数代表 $num\{\}$。

第一行一个正整数代表答案。

对于 $15\%$ 的数据，$N \leq 10$； 对于 $25\%$ 的数据，$N \leq 10^2$； 对于 $65\%$ 的数据，$N \leq 5 \cdot 10^3$； 对于 $100\%$ 的数据，$N \leq 1.3 \cdot 10^4$。(出题人卡了 $N^2$ 的空间 , 不过出题人用 $\texttt{Pascal}$ 已经 $\texttt{A}$ 过 , 所以不必担心因为常数被卡) 保证数据随机。 样例 $1$ 解释 : 首先，说说如何在 $X\{\}$ 中求 $A\{\}$。 假如 $X\{\}=(1,-3,4,2,-1,7)$，那么最大的区间就应该是 $(4,2,-1,7)$，和为 $12$，大于其它区间的和。 再假如 $X\{\}=(-3)$，显然最大的和为 $0$。 样例构图 :  你可以计算一下 $1+0+4+2+0+7+1+4+6+2+7+4+6+6+8+6+6+12+6+12+12$。