题目背景

（请先学习树状数组） ICPC World Finals 的赛场上，气氛凝重。比赛只剩最后两小时，队伍遇到了前所未有的防 AK 压轴大题。 此时，神级队友 jiangly 开启了“人机合一”模式，双手在键盘上化作残影，疯狂输出代码。Jiangrc 学长作为队伍的战术核心，负责在一旁实时审查 jiangly 敲出的每一段逻辑。 jiangly 将代码切分成了 $N$ 个逻辑块，每个逻辑块都有一个“灵光值”（有正有负，负数代表写法稍显冗余或有潜在的常数瓶颈）。 为了向后人传授 jiangly 的神级代码风格，Jiangrc 需要分析出所有可能的连续代码片段（即所有可能的子数组）的整体质量，并找出这些片段总灵光值的中位数。

题目描述

给定一个长度为 $N$ 的整数数组 $A$，表示 jiangly 敲出的各代码块的灵光值。 数组中总共有 $M = \frac{N(N+1)}{2}$ 个非空连续子数组。 你需要求出这 $M$ 个子数组的和从小到大排序后的第 $\lceil \frac{M}{2} \rceil$ 个值（向上取整，即中位数）。

输入格式

第一行包含一个正整数 $N$（$1 \le N \le 10^5$）。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$-10^4 \le A_i \le 10^4$）。

输出格式

输出一个整数，表示所有子数组和的中位数。

样例

4
2 -1 3 -2

1

样例解释

共有 $10$ 个代码片段，它们的总灵光值分别为： 长度 1: 2, -1, 3, -2 长度 2: 1, 2, 1 长度 3: 4, 0 长度 4: 2 排序后为：-2, -1, 0, 1, 1, 2, 2, 2, 3, 4。 $M = 10$，$\lceil 10/2 \rceil = 5$，第 $5$ 小的值是 $1$。