Tema 和 Vika 正在玩以下游戏。
首先,Vika 提出一个长度为 $$$m$$$ 的正整数序列 $$$a$$$ 并将其写在一张纸上。然后她拿出一张新纸,根据以下规则写下序列$$$b$$$:
- 首先,她写下$$$a_1$$$。
- 然后,她只写下那些 $$$a_i$$$ ($$$2 \le i \le m$$$) 使得 $$$a_{i - 1} \le a_i$$$。令该序列的长度表示为$$$n$$$。
例如,从序列$$$a=[4, 3, 2, 6, 3, 3]$$$,Vika将获得序列$$$b=[4, 6, 3]$$$。
然后,她将这张带有 $$$b$$$ 序列的纸交给了 Tema。反过来,他尝试猜测序列 $$$a$$$。
Tema 认为在这样一场游戏中获胜的可能性极小,但仍然希望找到至少一个可以由 Vika 最初选择的序列 $$$a$$$。帮助他并输出任何这样的序列。
请注意,输出序列的长度不应超过输入序列长度的两倍。
输入
每个测试由多个测试用例组成。输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 序列 $$$b$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — 序列的元素。
所有测试用例的 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出两行。在第一行中,输出单个整数 $$$m$$$ — 序列的长度 ($$$n \le m \le 2 \cdot n$$$)。在第二行中,输出 $$$m$$$ 整数 $$$a_1, a_2, a_3, \dots, a_m$$$ ($$$1 \le a_i \le 10^9$$$) - Vika 可能在第一张纸上写下的假设序列。
如果有多个合适的序列,则可以输出其中任何一个。
示例
输入 #1
6 3 4 6 3 3 1 2 3 5 1 7 9 5 7 1 144 2 1 1 5 1 2 2 1 1
输出 #1
6 4 3 2 6 3 3 3 1 2 3 6 1 7 9 3 5 7 1 144 2 1 1 6 1 2 2 1 1 1
注意
第一个示例在问题陈述中进行了解释。
在第二个样本中,Vika 可以选择原始序列。