序列 $$$[s_1, s_2, \ldots, s_d]$$$ 的得分定义为 $$$\displaystyle \frac{s_1\cdot s_2\cdot \ldots \cdot s_d}{d!}$$$,其中 $$$d!=1\cdot 2\cdot \ldots \cdot d$$$。特别地,空序列的分数是$$$1$$$。
对于序列 $$$[s_1, s_2, \ldots, s_d]$$$,令 $$$m$$$ 为其所有子序列中的最大得分。其成本定义为得分为 $$$m$$$ 的子序列的最大长度。
给你一个长度为$$$n$$$的整数的非递减序列$$$[a_1, a_2, \ldots, a_n]$$$。换句话说,满足条件 $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$。对于每个 $$$k=1, 2, \ldots , n$$$,求序列 $$$[a_1, a_2, \ldots , a_k]$$$ 的成本。
如果 $$$x$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$y$$$ 获得,则序列 $$$x$$$ 是序列 $$$y$$$ 的子序列。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 10^5$$$) — 给定序列的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\leq n$$$) — 给定序列。保证其元素按非降序排列。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$n$$$ 整数 - 序列 $$$[a_1, a_2, \ldots , a_k]$$$ 的成本,按 $$$k$$$ 升序排列。
示例
输入 #1
3 3 1 2 3 2 1 1 5 5 5 5 5 5
输出 #1
1 1 2 1 1 1 2 3 4 5
注意
在第一个测试用例中:
- $$$[1]$$$ 的子序列中的最大分数是 $$$1$$$。子序列 $$$[1]$$$ 和 $$$[]$$$ (空序列)是唯一具有此分数的序列。因此,$$$[1]$$$ 的成本为$$$1$$$。
- $$$[1, 2]$$$ 子序列中的最大得分为 $$$2$$$。具有此分数的唯一子序列是 $$$[2]$$$。因此,$$$[1, 2]$$$ 的成本为$$$1$$$。
- $$$[1, 2, 3]$$$ 的子序列中的最大分数是 $$$3$$$。子序列 $$$[2, 3]$$$ 和 $$$[3]$$$ 是唯一具有此分数的序列。因此,$$$[1, 2, 3]$$$ 的成本为 $$$2$$$。