考虑以下问题:给定一个包含 $$$n$$$ 整数的数组 $$$a$$$(索引从 $$$0$$$ 到 $$$n-1$$$),找到 $$$\max\limits_{0 \leq l \leq r \leq n-1} \sum\limits_{l \leq i \leq r} (r-l+1) \cdot a_i$$$。在这个问题中,$$$1 \leq n \leq 2\,000$$$ 和 $$$|a_i| \leq 10^6$$$。
为了解决所描述的问题,爱丽丝很快想出了一个极快的贪婪算法并对其进行了编码。她的伪代码实现如下:
另外,正如你所看到的,Alice 的想法并不完全正确。例如,假设 $$$n = 4$$$ 且 $$$a = [6, -8, 7, -42]$$$。然后,find_answer(n, a) 将返回 $$$7$$$,但正确答案是 $$$3 \cdot (6-8+7) = 15$$$。
你告诉Alice她的解决方案是不正确的,但她不相信你所说的。
给定一个整数 $$$k$$$,您需要找到 $$$n$$$ 整数的任何序列 $$$a$$$,使得正确答案和 Alice 算法生成的答案恰好相差 $$$k$$$。请注意,虽然 $$$n$$$ 和序列内容的选择是你的,但你仍然必须遵循前面给出的约束:$$$1 \leq n \leq 2\,000$$$ 并且每个元素的绝对值不超过 $$$10^6$$$。如果不存在这样的顺序,则确定。
输入
第一行也是唯一一行包含一个整数 $$$k$$$ ($$$1 \leq k \leq 10^9$$$)。
输出
如果没有找到的序列,则打印“-1”。
否则,在第一行中,打印一个整数 $$$n$$$ ($$$1 \leq n \leq 2\,000$$$),表示序列中元素的数量。
然后,在第二行中,打印 $$$n$$$ 以空格分隔的整数:$$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$|a_i| \leq 10^6$$$)。
示例
输入 #1
8
输出 #1
4 6 -8 7 -42
输入 #2
612
输出 #2
7 30 -12 -99 123 -2 245 -300
注意
第一个示例对应于问题陈述中给出的示例。
在第二个示例中,一个答案是 $$$n = 7$$$,其中 $$$a = [30, -12, -99, 123, -2, 245, -300]$$$,在这种情况下 find_answer(n, a) 返回 $$$1098$$$,而正确答案是 $$$1710$$$。