这是问题的简单版本。版本之间的区别在于,在简单版本中,所有价格 $$$a_i$$$ 都不同。当且仅当您解决了问题的两个版本时,您才可以进行黑客攻击。
今天是Sage的生日,她要去逛街买冰球。所有 $$$n$$$ 冰球都排成一排,从左到右编号为 $$$1$$$ 到 $$$n$$$。每个冰球都有一个正整数价格。 In this version all prices are different.
如果一个冰球的成本严格低于两个相邻的冰球(最左边的和最右边的),那么它就是便宜的。最左边和最右边的冰球并不便宜。贤者会选择所有便宜的冰球,然后只购买它们。
您可以在Sage之前访问商店并根据需要重新订购冰球。找出 Sage 可以购买的最大冰球数量,并展示如何重新排序冰球。
输入
第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 10^5)$$$ — 商店中冰球的数量。
第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — 冰球的价格。
输出
在第一行打印 Sage 可以购买的最大冰球数量。
在第二行中以最佳顺序打印冰球的价格。如果有多个正确答案,您可以打印其中任何一个。
示例
输入 #1
5 1 2 3 4 5
输出 #1
2 3 1 4 2 5
注意
在示例中,不可能以任何顺序放置冰球,以便 Sage 购买 $$$3$$$ 的冰球。如果冰球像这样放置 $$$(3, 1, 4, 2, 5)$$$,那么 Sage 会购买两个冰球:一个价值 $$$1$$$,另一个价值 $$$2$$$,因为它们很便宜。