解题思路

• 核心转化 要让第 i 条鱼被吃掉，必须先在它一侧（左或右）“造”出一个紧邻它、血量严格大于 a_i 的块。造块的方式就是同侧若干条相邻鱼互相吞吃并合并为一个块（每次由较大者吃较小者）。 若这侧最终用到 m 条鱼把它们合成一个块再吃掉 i，总操作次数就是：块内合并 m-1 次 + 最后吃 i 的 1 次，共 m 次。因此，对每个 i，答案是左右两侧中能达到 sum > a_i 的最短相邻窗口长度的最小值（若两侧都不行则为 -1）。

• 关键细节：严格大于与“全相等”窗口 所有血量为正数，因此同侧窗口长度随扩展单调增加，最短超过 a_i 的窗口可用前缀和 + 二分直接定位。 但若该窗口长度 m≥2 且窗口内元素全相等，则它们互相都不是“严格大于”，无法发生任何一次吞吃，不能被合并成块。此时必须再把窗口再向外扩 1 个不同值进入窗口，窗口才可合并。 为了 O(1) 判断“是否全相等”，预处理相等段：

题目内容

多多在玩大鱼吃小鱼的游戏，目前有 $n$ 条鱼，编号从 $1$ 到 $n$ 按顺序排列，第 $i$ 条鱼的血量记为 $a_i$ 。

该游戏有以下规则：一条鱼只有在它的血量严格大于(不包含等于)它相邻的鱼时，它才能吃掉这条相邻的鱼，并且增加自身血量，增加值等于被吃掉的鱼的血量。如果没有任何一条鱼的血量严格大于它的邻居，则游戏结束。

例如，有 $n=5，a=[2,2,3,1,4]$ 。该过程可能如下进行：

首先，第 $3$ 条鱼吃掉第 $2$ 条鱼。第 $3$ 条鱼的血量变为 $5$ ，第 $2$ 条鱼被吃掉。

然后，第 $3$ 条鱼吃掉第 $1$ 条鱼(由于第 $2$ 条鱼已被吃掉，他们现在是相邻的)。第 $3$ 条鱼的血量变为 $7$ ，第 $1$ 条鱼被吃掉。

接着，第 $5$ 条鱼吃掉第 $4$ 条鱼。第 $5$ 条鱼的血量变为 $5$，第 $4$ 条鱼被吃掉。

最后，第 $3$ 条鱼吃掉第 $5$ 条鱼(由于第 $4$ 条鱼已被吃掉，他们现在是相邻的)。第 $3$ 条鱼的血量变为 $12$ ，第 $5$ 条鱼被吃掉。

请问：对于每一条鱼，计算在所有可能的进食顺序中，它被其他鱼吃掉所需的最少次数是多少？如果它不可能被吃掉，则输出 $-1$ 。

输入描述

共 $2$ 行，第一行包含一个正整数 $n$ ，表示鱼的数量。$(1<=n<=10^5)$

第 $2$ 行包含 $n$ 个正整数: $a_1,a_2,...,a_n(1<=n<=10^5)$，表示每条鱼的血量。

测试样例中 $n$ 条鱼的血量之和不会超过 $10^{10}$ 。

输出描述

共 $1$ 行，每行输出 $n$ 个整数。第 $i$ 个整数表示第 $i$ 条鱼被其他鱼吃掉所需的最少次数；

如果不可能被吃掉，则输出 $-1$ 。

样例1

输入

4
3 2 4 2

输出

2 1 2 1

样例2

输入

3
1 2 3

输出

1 1 -1

样例3

输入

5
2 2 3 1 1

输出

2 1 -1 1 2