区间最值¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境与测量见评测说明。
背景故事¶
观测站记录了一列测量值。为了比较不同观测时段，研究员想知道每个连续时段中较大的一半测量值之和。
(本故事由GPT-6重写)
形式化问题描述¶
给定长度为 \(n\) 的整数序列 \(a_1,\ldots,a_n\) .对每个非空连续区间 \([l,r]\) ，令 \(L=r-l+1\) ，求区间中最大的 \(\lceil L/2\rceil\) 个元素之和。
相等的数按不同位置分别计数。即使数值为负，也必须恰好选择指定数量的元素。
输入格式¶
第一行一个整数 \(n\) .第二行 \(n\) 个整数 \(a_1,\ldots,a_n\) .
输出格式¶
输出 \(n(n+1)/2\) 行，每行一个整数。先按区间长度递增排序，同长度按左端点递增排序。
例如 \(n=3\) 时依次对应 \([1,1]\) 、\([2,2]\) 、\([3,3]\) 、\([1,2]\) 、\([2,3]\) 、\([1,3]\) .
样例¶
样例 1¶
输入¶
5
2 3 9 9 1
输出¶
2
3
9
9
1
3
9
9
9
12
18
18
18
18
21
样例 2¶
输入¶
4
-5 0 -5 8
输出¶
-5
0
-5
8
0
0
8
-5
8
8
样例 3¶
输入¶
1
1000000000
输出¶
1000000000
样例解释¶
第一组样例的整个区间排序后为 \(1,2,3,9,9\) ，最大的三个元素之和为 \(21\) .第二组样例中，长度为一的区间仍需选择其中的负数。
图中 \(b_i\) 表示排序后的第 \(i\) 个数。虚线框包含较大的三个数；下方同时标出中间元素的二倍，便于区分两个统计量。
数据范围与保证¶
所有数据满足：\(1\le n\le10^3\) ，\(\lvert a_i\rvert\le10^9\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |