整数数组 $$$a_1, a_2, \ldots, a_n$$$ 的最长非递减子序列是最长索引序列 $$$1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n$$$ 使得 $$$a_{i_1} \leq a_{i_2} \leq \ldots \leq a_{i_k}$$$。序列的长度定义为序列中元素的数量。例如,数组 $$$a = [3, 1, 4, 1, 2]$$$ 的最长非递减子序列的长度为 $$$3$$$。
给定两个整数数组 $$$l_1, l_2, \ldots, l_n$$$ 和 $$$r_1, r_2, \ldots, r_n$$$。对于每个 $$$1 \le k \le n$$$,解决以下问题:
- 考虑长度为 $$$k$$$ 的所有整数数组 $$$a$$$,这样对于每个 $$$1 \leq i \leq k$$$,它保持 $$$l_i \leq a_i \leq r_i$$$。找到所有此类数组中最长非递减子序列的最大长度。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$l$$$ 和 $$$r$$$ 的长度。
每个测试用例接下来的 $$$n$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$n$$$ 整数:对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,输出所有合适数组中最长非递减子序列的最大长度。
示例
输入复制
611 123 41 244 53 41 33 386 84 63 55 53 41 32 43 351 26 84 52 33 31135 12066 22941 26698 16455 153125 174139 23730 72138 212109 123174 196
输出复制
1 1 1 1 2 2 3 1 2 2 3 3 3 4 5 1 2 2 2 3 1 2 3 4 5 6 7 7 8 8 9
注意
在第一个测试用例中,唯一可能的数组是 $$$a = [1]$$$。该数组的最长非递减子序列的长度为$$$1$$$。
在第二个测试用例中,对于 $$$k = 2$$$,无论我们如何选择 $$$a_1$$$ 和 $$$a_2$$$ 的值,条件 $$$a_1 \gt a_2$$$ 将始终成立。因此,$$$k = 2$$$ 的答案将是 $$$1$$$。
在第三个测试用例中,对于$$$k = 4$$$,我们可以选择数组$$$a = [5, 3, 3, 3]$$$。该数组的最长非递减子序列的长度为$$$3$$$。
在第四个测试用例中,对于$$$k = 8$$$,我们可以选择数组$$$a = [7, 5, 3, 5, 3, 3, 3, 3]$$$。该数组的最长非递减子序列的长度为$$$5$$$。
在第五个测试用例中,对于$$$k = 5$$$,我们可以选择数组$$$a = [2, 8, 5, 3, 3]$$$。该数组的最长非递减子序列的长度为$$$3$$$。