题目描述

序列 [s1, s2, …, sd] 的得分定义为 (s1 × s2 × … × sd) / d!，其中 d! = 1 × 2 × … × d。空序列的得分为 1。

对于一个序列 [a1, a2, …, an]，假设 m 为其所有子序列中的最大得分，其代价 s 定义为该序列所有得分为 m 的子序列中长度最大的序列的长度。

如果 x 可以从 y 中删除几个（可能是零个或全部）元素而得到，则序列 x 是序列 y 的子序列。

输入格式

每个测试用例包含多个测试用例。第一行包含测试用例的数量 t（1 <= t <= 10⁴），测试用例说明如下。

每个测试用例的第一行都包含一个整数 n（1 <= n <= 10⁹）——给定序列的长度。

每个测试用例的第二行包含 n 个整数 a1, a2, …, an（1 <= ai <= n）——给定序列。保证其元素不减。

保证所有测试用例中 n 的总和不超过 5 × 10⁵。

输出格式

对于每个测试用例，输出 n 个整数——按 k 升序排列的 [a1, a2, …, ak] 序列的代价。

3
3
1 2 3
2
1 1
5
5 5 5 5 5

1 1 2
1 1
1 2 3 4 5

</p>

提示

第 1 个测试用例：在 [1] 的子序列中，最大得分是 1，只有子序列 [1] 和 []（空序列）达到了这个水平，因此 [1] 的代价是 1；在 [1,2] 的子序列中，最大得分是 2，唯一具有此得分的子序列是 [2]，因此 [1,2] 的代价是 1；在 [1,2,3] 的子序列中，最大得分是 3，只有子序列 [2,3] 和 [3] 有此得分，因此 [1,2,3] 的代价为 2。所以本题的答案为 1 1 2。

第 2 个测试用例（序列 1 1）输出 1 1；第 3 个测试用例（序列 5 5 5 5 5）输出 1 2 3 4 5。

来源

二分查找