P11551 [ROIR 2016] 奖品 (Day 1)

翻译自 [ROIR 2016 D1T1](https://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-regional-2016-day1.pdf)。

Petya 参加了一个比赛，在这个比赛中将会抽取 $n$ 个奖品。奖品编号从 $1$ 到 $n$。 根据比赛结果，参赛者可以获得 $2$ 到 $n$ 之间的分数。如果参赛者获得了 $k$ 分，那么他将从编号 $1$ 到 $k$ 的奖品中获得一个奖品。比赛主持人在参赛者选择奖品之前，会从奖品列表中删除一个奖品。然后，参赛者可以从剩下的 $k - 1$ 个奖品中选择一个。 Petya 知道所有奖品的价值，第 $i$ 个奖品的价值为 $a_i$。 对于每个 $2\le k\le n$，你需要求出如果 Petya 获得了 $k$ 分，他一定能得到的最大奖品价值是多少。

无

无

| 子任务 | 是否捆绑 | 分值 | $1\le n\le$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | 是 | $24$ | $100$ | | $2$ | 是 | $24$ | $5000$ | | $3$ | 是 | $52$ | $100000$ |