UOJ Logo Universal Online Judge

UOJ

#245. 【UER #7】天路

统计

隆冬将至,几天后跳蚤国便会迎来寒冬,这对于以血肉之躯和飞机搏斗的跳蚤们来说并不是件好事……然而在悠悠历史岁月中,跳蚤国早已有了应对严寒的应急措施方案!

在跳蚤国王的带领下,跳蚤们准备启动天路热能塔 —— 红米 note7(红米 note7 为发烧而生)。这座热能塔高耸入云,直接穿出大气层从太空中直接吸收太阳光,垂直向下将热能送往跳蚤国各个角落。热能塔的制造工艺巧夺天工,被誉为“带来温暖的天路”。

但是跳晚们为了让跳蚤们都因为天气寒冷赖在被子里不肯起床,在热能塔启动后一定会歇斯底里地进攻。跳蚤国高级间谍的情报显示,跳晚国计划将发射 $n$ 台三星 note7 向热能塔发起进攻。进攻将会按一定顺序进行,其中第 $i$ 次进攻的高度为 $a_i$ ($1 \le i \le n$)。

为了防止热能塔被炸毁,跳蚤国王特地派尛焱轟(一种新型交通工具,运载能力是小火车的三次幂)运送来了跳蚤们刚研制出不久的新型材料 —— Nokia1050。跳蚤们将会把 Nokia1050 装在热能塔上的某一连续的高度区间上以抵挡进攻。

现在,跳蚤国王想在热能塔受损程度和材料消耗量之间进行取舍。所以对于每个 $2 \le k \le n$,跳蚤国王想知道整个攻击过程中如果想让 Nokia1050 在某一时段至少挡住连续 $k$ 次攻击,那么安装 Nokia1050 的高度区间的长度至少是多少。其中,若高度区间为 $[l, r]$,则长度为 $r - l$。

事实上,间谍的消息也不见得会多么靠谱,所以跳蚤国王仅想知道一个不那么准确的答案。具体来说:

如果对于每个 $k$ 你输出的答案 $c_k$ 与标准答案 $\hat{c}_k$ 的相对误差均不超过 $5\%$,则算作正确。即: \begin{equation} \lvert c_k - \hat{c}_k \rvert \le 5\% \cdot \hat{c}_k \end{equation}

输入格式

第一行一个正整数 $n$,保证 $n \ge 2$。

第二行 $n$ 个正整数 $a_1, \dots, a_n$,按顺序给出每次进攻时三星 note7 的高度。

输出格式

输出 $n - 1$ 行,其中第 $k - 1$ 行表示至少抵挡连续 $k$ 次攻击时所需的最短高度区间长度。($2 \le k \le n$)

因为十分重要所以说两遍,如果对于每个 $k$ 你输出的答案 $c_k$ 与标准答案 $\hat{c}_k$ 的相对误差均不超过 $5\%$,则算作正确。即: \begin{equation} \lvert c_k - \hat{c}_k \rvert \le 5\% \cdot \hat{c}_k \end{equation}

样例一

input

4
1 7 5 2

output

2
5
6

explanation

当 $k = 2$ 时,最优高度区间为 $[5, 7]$;

当 $k = 3$ 时,最优高度区间为 $[2, 7]$;

当 $k = 4$ 时,最优高度区间为 $[1, 7]$。

注意 $k = 2$ 时不能选择高度区间 $[1, 2]$,虽然能够拦截下第 $1$ 次和第 $4$ 次攻击,但这两次攻击并不连续。

样例二

input

10
26 723 970 13 422 968 875 329 234 983

output

93
546
639
734
749
957
957
957
970

explanation

样例输出给出的为准确答案,注意下面的输出也是可接受的:

93
540
630
730
740
960
960
960
970

样例三

见样例数据下载。

限制与约定

测试点编号 $n$ 的规模 特殊限制
1$n \le 100$$a_i \le 100$
2
3
4$n \le 1000$
5
6$n \le 10^5$每个 $a_i$ 均是从 $[1, 10^6]$ 中独立选取的均匀随机整数
7
8
9
10

对于所有数据,保证 $1 \le a_i \le 10^6$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载

后记

最后跳蚤国保住了热能塔,并且跳蚤国王发现,进入隆冬之后跳晚国的轰炸次数变得越来越少了。原来,不适应在严寒中作战的跳晚国士兵惧怕寒冷变得越来越晚起床了。

“是时候展开反攻了!”