二分炼狱
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述


塑料因为滥用 partition_point 被打入了二分炼狱，橘猫大人给他分配的第一个工作是 “给定一个正整数序列，询问下标查找右边第一个比它大/小的数字”。


“这不是我们 2023 新生月赛的题目吗，下次记得标明出处”，塑料洋洋洒洒地写了个线段树上二分（尽管这次并不需要修改）交了上去。


然而没过几天，橘猫发现塑料的代码出锅了。愤怒的橘猫给塑料发布了他的第二个工作：


定义一个函数 f(x)，它的工作方式是按顺序执行


  1. 初始时，下标 \textstyle pos = x, value = a_{pos}, 所求和 sum = 0。


  2. 找到 pos 右边第一个 pos'，使得 \textstyle a_{pos'} > value，令 sum 增加 a_{pos'}，pos 修改为 pos'；
    若找不到，返回 sum，结束。


  3. 找到 pos 右边第一个 pos'，使得 \textstyle a_{pos'} < value，令 sum 增加 a_{pos'}，pos 修改为 pos'；
    若找不到，返回 sum，结束。


  4. 重新回到第 2 步。


塑料随便一想就想出了 f(x) 的求法，然而橘猫大人让塑料别得意得太早，因为他希望对于每一个 i (1 \le i \le n) 都要求出 f(i) 的值。


汗流浃背的塑料发现时限只有 1ms，他找到了v2x1求他帮忙卡卡常数。v2x1一边流汗一边跟橘猫商量，最后橘猫同意塑料只需要在两秒内搞定。


然而就算如此塑料还是不会做，所以他来找你了，请你帮帮他吧。

输入描述:

第一行输入一个正整数 n (1 \leq n \leq 2 \times 10^5)

接下来输入 n 个正整数 a_1,a_2,\dots,a_n (1 \leq a_i \leq 10^9)，表示塑料需要处理的序列。

输出描述:

设 b_i 为第 i 个元素带入 f(x) 的返回值，你需要输出一个长度为 n 的正整数序列 b_1,b_2,...,b_n，元素之间用空格隔开。
示例1

输入

复制 
6
1 1 4 5 1 4

输出

复制 
4 4 6 0 4 0

备注:

样例解释：

对于第一个元素，第一个比它大的数是 4，而之后就没有比 1 小的数字了，所以 b_1 = 4。

对于第三个元素，第一个比它大的数是 5，接下来比它小的第一个数字是 1，所以 b_3 = 5 + 1 = 6。