有 $$$n$$$ 史莱姆排成一行。史莱姆按从左到右的顺序从 $$$1$$$ 到 $$$n$$$ 编号。第 $$$i$$$ 个史莱姆的大小为 $$$a_i$$$。
每一秒,都会发生以下情况:恰好有一个史莱姆吃掉了它的邻居之一,并根据被吃掉的邻居的大小增加了自己的大小。只有当史莱姆严格大于邻居时,它才能吃掉它的邻居。如果没有严格大于其邻居之一的史莱姆,则该过程结束。
例如,假设 $$$n = 5$$$,$$$a = [2, 2, 3, 1, 4]$$$。该过程可以如下进行:
- 首先,$$$3$$$-rd 史莱姆吃掉了 $$$2$$$-nd 史莱姆。 $$$3$$$-rd 史莱姆的大小变为 $$$5$$$,$$$2$$$-nd 史莱姆被吃掉。
- 然后,$$$3$$$-rd 史莱姆吃掉了 $$$1$$$-st 史莱姆(它们是邻居,因为 $$$2$$$-nd 史莱姆已经被吃掉了)。 $$$3$$$-rd 史莱姆的大小变为 $$$7$$$,$$$1$$$-st 史莱姆被吃掉。
- 然后,第 $$$5$$$ 个史莱姆吃掉了第 $$$4$$$ 个史莱姆。第 $$$5$$$ 个史莱姆的大小变为 $$$5$$$,第 $$$4$$$ 个史莱姆被吃掉。
- 然后,第 $$$3$$$ 个史莱姆吃了第 $$$5$$$ 个史莱姆(它们是邻居,因为第 $$$4$$$ 个史莱姆已经被吃掉了)。第 $$$3$$$ 个史莱姆的大小变为 $$$12$$$,第 $$$5$$$ 个史莱姆被吃掉。
对于每个史莱姆,计算该史莱姆被另一个史莱姆吃掉所需的最短秒数(在该过程的所有可能方式中),或者报告这是不可能的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 史莱姆的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,打印 $$$n$$$ 整数。第 $$$i$$$ 个整数应等于第 $$$i$$$ 个史莱姆被另一个史莱姆吃掉所需的最小秒数,如果不可能,则为 -1。
示例
输入 #1
4 4 3 2 4 2 3 1 2 3 5 2 2 3 1 1 7 4 2 3 6 1 1 8
输出 #1
2 1 2 1 1 1 -1 2 1 -1 1 2 2 1 1 3 1 1 4