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

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

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

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

1. 初始时，下标 $$$pos = x$$$, $$$value = a_{pos}$$$ 所求和 $$$sum = 0$$$。
2. 找到 $$$pos$$$ 右边第一个 $$$pos'$$$，使得 $$$a_{pos'} \gt value$$$，令 $$$sum$$$ 增加 $$$a_{pos'}$$$，$$$pos$$$ 修改为 $$$pos'$$$； 若找不到，返回 sum，结束。
3. 找到 $$$pos$$$ 右边第一个 $$$pos'$$$，使得 $$$a_{pos'} \lt value$$$，令 $$$sum$$$ 增加 $$$a_{pos'}$$$，$$$pos$$$ 修改为 $$$pos'$$$； 若找不到，返回 sum，结束。
4. 重新回到第 2 步。

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

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

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