#P17982. Potential Peak

Potential Peak

Potential Peak

题目描述

共有 nn 天,第 ii 天加入一名初始能力为 aia_i 的成员,其编号为 ii。

在第 kk 天结束时,对每名 i≤ki\le k 的成员分别进行一次假想计算:他可以选择任意非负整数 ee,花费 ee 单位努力,把自己的能力临时提高到 ai+ea_i+e。

对于每名满足 i<j≤ki<j\le k 且 ai<aj≤ai+ea_i<a_j\le a_i+e 的成员 jj,他得到 11 单位收益。其潜力值定义为“收益减去努力”所能达到的最大值,即

$$P_i(k)=\max_{e\in\mathbb Z_{\ge0}}\left(\#\{j:i<j\le k,\ a_i<a_j\le a_i+e\}-e\right).$$

这些计算彼此独立,而且不会真正修改任何人的能力。求每一天结束时所有现有成员的潜力值之和。

输入格式

第一行一个整数 nn。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

输出一行 nn 个整数,第 kk 个数为 ∑i=1kPi(k)\sum_{i=1}^kP_i(k)。

数据范围

1≤n≤1051\le n\le10^5,1≤ai≤n1\le a_i\le n。

样例 1

8
1 2 3 1 2 3 2 3
0 0 0 0 1 3 5 9

第 55 天,编号 11 的成员花费 11,可以得到编号 2,52,5 的两份收益,净收益为 11;其余成员潜力均为 00。

样例 2

1
1
0