← 返回题目列表

Codeforces · 1802/A

A. 喜欢

中文机器翻译题面 查看原题

Nikita 最近进行了一场非常有争议的回合,此后他的贡献变化很快。

该公告在主页上挂了 $$$n$$$ 秒。在第 $$$i$$$ 第二个 $$$|a_i|$$$ 中,第 $$$|a_i|$$$ 个人要么点赞,要么删除点赞(尼基塔在这项任务中很幸运,没有不喜欢的人)。如果 $$$a_i > 0$$$,则第 $$$a_i$$$ 人点赞。如果 $$$a_i < 0$$$,则 $$$-a_i$$$ 删除了类似内容。每个人放置和移除类似物品的次数不超过一次。如果一个人之前没有点过赞,那么他就无法删除它。

由于Nikita在这一轮之后的贡献度变得非常差,他想分析一下在主页上发布公告的同时,他的贡献度发生了怎样的变化。他向平台的创建者请求提供序列 $$$a_1, a_2, \ldots, a_n$$$。但由于平台的不完善,$$$a$$$的顺序被打乱了。

您将获得一个描述用户活动的 $$$a$$$ 打乱序列。您需要知道从 $$$1$$$ 到 $$$n$$$ 的每个时刻,该帖子的最大和最小点赞数是多少。

输入

输入数据的第一行包含一个数字 $$$t$$$ ($$$1 \leqslant t \leqslant 1000$$$) — 测试用例的数量。

在测试用例的第一行中,给出了一个数字 $$$n$$$ ($$$1 \leqslant n \leqslant 100$$$) — Nikita 的公告在主页上挂起的秒数。

下一行包含 $$$n$$$ 数字 $$$b_1, b_2, b_3, \ldots, b_n$$$ ($$$1 \leqslant |b_i| \leqslant n$$$) — 混合数组 $$$a$$$。保证存在这样的 $$$b$$$ 排列,它是条件中描述的事件的正确序列。

保证所有输入测试用例的$$$n$$$总和不超过$$$10^4$$$。

输出

对于每个测试用例,输出两行,每行包含 $$$n$$$ 数字。

在第一行中,对于每个测试用例,输出 Nikita 在第 $$$i$$$ 秒的公告中可能获得的最大点赞数。

在第二行中,对于每个测试用例,输出 Nikita 在第 $$$i$$$ 秒的公告中可能获得的最小点赞数。

示例

输入 #1

5
3
1 2 -2
2
1 -1
6
4 3 -1 2 1 -2
5
4 2 -2 1 3
7
-1 6 -4 3 2 4 1

输出 #1

1 2 1 
1 0 1 
1 0 
1 0 
1 2 3 4 3 2 
1 0 1 0 1 2 
1 2 3 4 3 
1 0 1 2 3 
1 2 3 4 5 4 3 
1 0 1 0 1 2 3

注意

在第一个测试用例中,通过以下排列达到最大值:$$$1, 2, -2$$$。其最小值为:$$$2、-2、1$$$。

在第三个测试用例中,通过以下排列达到所有最大值:$$$4, 2, 3, 1, -1, -2$$$。下一个排列的最小值:$$$2, -2, 1, -1, 3, 4$$$。