# 区间中位数

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境与测量见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

观测站记录了一列测量值。研究员需要每个连续时段的中位数，并约定把结果乘以二后报告，以便始终输出整数。

(本故事由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

### 输入

```text
5
2 3 9 9 1
```

### 输出

```text
4
6
18
18
2
5
12
18
10
6
18
18
12
12
6
```

### 样例 2

### 输入

```text
4
-5 0 -5 8
```

### 输出

```text
-10
0
-10
16
-5
-5
3
-10
0
-5
```

### 样例 3

### 输入

```text
1
-1000000000
```

### 输出

```text
-2000000000
```

## 样例解释

第一组样例的整个区间排序后为 $1,2,3,9,9$ ，中位数的二倍为 $6$ .区间 $[1,2]$ 的中位数为 $2.5$ ，输出 $5$ .

![五个排序后元素的中位数及较大一半](assets/partition.svg)

虚线框标出较大的三个数，括号标出中间元素 $b_3$ .本题取中位数的二倍，即 $6$ .

## 数据范围与保证

所有数据满足：$1\le n\le10^3$ ，$\lvert a_i\rvert\le10^9$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |