Scoring Subsequences

题意翻译

定义序列 $[s_1,s_2,\cdots,s_d]$ 的*得分*为 $$\frac{s_1 \cdot s_2 \cdot \dots \cdot s_d}{d!}$$ 特别地，空序列的得分为 $1$。 定义序列 $[s_1,s_2,\cdots,s_d]$ 的*花费*为原序列中取得最大得分的所有子序列，其中最长的一个子序列的长度。 给定单调不减序列 $[a_1,a_2,\dots,a_n]$，对每个 $k=1,2,\cdots n$，求 $[a_1,a_2,\cdots ,a_k]$ 的花费。 规定某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

题目描述

The score of a sequence $ [s_1, s_2, \ldots, s_d] $ is defined as $ \displaystyle \frac{s_1\cdot s_2\cdot \ldots \cdot s_d}{d!} $ , where $ d!=1\cdot 2\cdot \ldots \cdot d $ . In particular, the score of an empty sequence is $ 1 $ . For a sequence $ [s_1, s_2, \ldots, s_d] $ , let $ m $ be the maximum score among all its subsequences. Its cost is defined as the maximum length of a subsequence with a score of $ m $ . You are given a non-decreasing sequence $ [a_1, a_2, \ldots, a_n] $ of integers of length $ n $ . In other words, the condition $ a_1 \leq a_2 \leq \ldots \leq a_n $ is satisfied. For each $ k=1, 2, \ldots , n $ , find the cost of the sequence $ [a_1, a_2, \ldots , a_k] $ . A sequence $ x $ is a subsequence of a sequence $ y $ if $ x $ can be obtained from $ y $ by deletion of several (possibly, zero or all) elements.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1\le n\le 10^5 $ ) — the length of the given sequence. The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1\le a_i\leq n $ ) — the given sequence. It is guaranteed that its elements are in non-decreasing order. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5\cdot 10^5 $ .

输出格式

For each test case, output $ n $ integers — the costs of sequences $ [a_1, a_2, \ldots , a_k] $ in ascending order of $ 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

说明

In the first test case: - The maximum score among the subsequences of $ [1] $ is $ 1 $ . The subsequences $ [1] $ and $ [] $ (the empty sequence) are the only ones with this score. Thus, the cost of $ [1] $ is $ 1 $ . - The maximum score among the subsequences of $ [1, 2] $ is $ 2 $ . The only subsequence with this score is $ [2] $ . Thus, the cost of $ [1, 2] $ is $ 1 $ . - The maximum score among the subsequences of $ [1, 2, 3] $ is $ 3 $ . The subsequences $ [2, 3] $ and $ [3] $ are the only ones with this score. Thus, the cost of $ [1, 2, 3] $ is $ 2 $ . Therefore, the answer to this case is $ 1\:\:1\:\:2 $ , which are the costs of $ [1], [1, 2] $ and $ [1, 2, 3] $ in this order.

**题意翻译**

定义序列 $[s_1,s_2,\cdots,s_d]$ 的*得分*为
$$\frac{s_1 \cdot s_2 \cdot \dots \cdot s_d}{d!}$$

特别地，空序列的得分为 $1$。

定义序列 $[s_1,s_2,\cdots,s_d]$ 的*花费*为原序列中取得最大得分的所有子序列，其中最长的一个子序列的长度。

给定单调不减序列 $[a_1,a_2,\dots,a_n]$，对每个 $k=1,2,\cdots n$，求 $[a_1,a_2,\cdots ,a_k]$ 的花费。

规定某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

**题目描述**

序列 $ [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 $ 的子序列中的最大长度。

给定一个单调不减的整数序列 $ [a_1, a_2, \ldots, a_n] $ 的长度 $ 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 $ 个整数——按 $ k $ 升序的序列 $ [a_1, a_2, \ldots , a_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 $ 。

因此，此案例的答案是 $ 1\:\:1\:\:2 $ ，它们是 $ [1], [1, 2] $ 和 $ [1, 2, 3] $ 的花费。**题意翻译** 定义序列 $[s_1,s_2,\cdots,s_d]$ 的*得分*为 $$\frac{s_1 \cdot s_2 \cdot \dots \cdot s_d}{d!}$$ 特别地，空序列的得分为 $1$。 定义序列 $[s_1,s_2,\cdots,s_d]$ 的*花费*为原序列中取得最大得分的所有子序列，其中最长的一个子序列的长度。 给定单调不减序列 $[a_1,a_2,\dots,a_n]$，对每个 $k=1,2,\cdots n$，求 $[a_1,a_2,\cdots ,a_k]$ 的花费。 规定某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。 **题目描述** 序列 $ [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 $ 的子序列中的最大长度。 给定一个单调不减的整数序列 $ [a_1, a_2, \ldots, a_n] $ 的长度 $ 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 $ 个整数——按 $ k $ 升序的序列 $ [a_1, a_2, \ldots , a_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 $ 。 因此，此案例的答案是 $ 1\:\:1\:\:2 $ ，它们是 $ [1], [1, 2] $ 和 $ [1, 2, 3] $ 的花费。