# 区间最值

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

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

## 背景故事

观测站记录了一列测量值。为了比较不同观测时段，研究员想知道每个连续时段中较大的一半测量值之和。

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

### 输入

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

### 输出

```text
2
3
9
9
1
3
9
9
9
12
18
18
18
18
21
```

### 样例 2

### 输入

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

### 输出

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

### 样例 3

### 输入

```text
1
1000000000
```

### 输出

```text
1000000000
```

## 样例解释

第一组样例的整个区间排序后为 $1,2,3,9,9$ ，最大的三个元素之和为 $21$ .第二组样例中，长度为一的区间仍需选择其中的负数。

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

图中 $b_i$ 表示排序后的第 $i$ 个数。虚线框包含较大的三个数；下方同时标出中间元素的二倍，便于区分两个统计量。

## 数据范围与保证

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

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