区间中位数¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境与测量见评测说明。
背景故事¶
观测站记录了一列测量值。研究员需要每个连续时段的中位数，并约定把结果乘以二后报告，以便始终输出整数。
(本故事由GPT-6重写)
形式化问题描述¶
给定长度为 \(n\) 的整数序列 \(a_1,\ldots,a_n\) .对每个非空连续区间 \([l,r]\) ，输出其中位数的二倍。
设区间长度为 \(L=r-l+1\) ，其元素按不降顺序排列为 \(b_1,\ldots,b_L\) .答案定义为
\[
b_{\lfloor(L+1)/2\rfloor}+b_{\lceil(L+1)/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
输出¶
4
6
18
18
2
5
12
18
10
6
18
18
12
12
6
样例 2¶
输入¶
4
-5 0 -5 8
输出¶
-10
0
-10
16
-5
-5
3
-10
0
-5
样例 3¶
输入¶
1
-1000000000
输出¶
-2000000000
样例解释¶
第一组样例的整个区间排序后为 \(1,2,3,9,9\) ，中位数的二倍为 \(6\) .区间 \([1,2]\) 的中位数为 \(2.5\) ，输出 \(5\) .
虚线框标出较大的三个数，括号标出中间元素 \(b_3\) .本题取中位数的二倍，即 \(6\) .
数据范围与保证¶
所有数据满足：\(1\le n\le10^3\) ，\(\lvert a_i\rvert\le10^9\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |