Rhodoks 给 AquaMoon 一个长度为 的序列 ,让她把 划分为两个子序列,使它们的和相等。
但是 AquaMoon 水平不行,所以希望你能帮她完成,这样她就可以和 Rhodoks 贴贴啦!
你只需要输出其中两个子序列中的一个,由于可能有很多解,AquaMoon 希望你能使解是所有方案里字典序最小的。
某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置(在前或在后)而形成的新序列。
考虑序列与, 考虑第一个在两个序列中对应元素不同的下标,如果则的字典序小于的字典序。 如果不存在这样的下标,即其中一个序列是另外一个序列的前缀,则短者字典序更小。
例如: