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

在跳蚤国王的带领下，跳蚤们准备启动天路热能塔 —— 红米 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

样例三

见样例数据下载。

限制与约定

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

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

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

下载

样例数据下载

后记

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

“是时候展开反攻了！”