P3850.第4题-大鱼吃小鱼
题目内容
多多在玩大鱼吃小鱼的游戏，目前有 n 条鱼，编号从 1 到 n 按顺序排列，第 i 条鱼的血量记为 ai 。
该游戏有以下规则：一条鱼只有在它的血量严格大于(不包含等于)它相邻的鱼时，它才能吃掉这条相邻的鱼，并且增加自身血量，增加值等于被吃掉的鱼的血量。如果没有任何一条鱼的血量严格大于它的邻居，则游戏结束。
例如，有 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<=105)
第 2 行包含 n 个正整数: a1,a2,...,an(1<=n<=105)，表示每条鱼的血量。
测试样例中 n 条鱼的血量之和不会超过 1010 。
输出描述
共 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
