← 返回题目列表

Codeforces · 1419/D1

D1. 圣人的生日(简易版)

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

这是问题的简单版本。版本之间的区别在于,在简单版本中,所有价格 $$$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$$$,因为它们很便宜。