问题描述

给你一个整数数组 nums，请将其重新排序，使得满足以下顺序：

nums[0] < nums[1] > nums[2] < nums[3] ...

你可以假设所有输入数组都可以得到满足题目要求的结果。

格式

输入

• 一个整数数组 nums，长度 n。

输出

• 重新排序后的 nums，满足 nums[0] < nums[1] > nums[2] < nums[3] ...。

样例

样例1

输入

1 5 1 6 4

输出

1 6 1 5 4

解释

[1,4,1,5,6] 也是符合题目要求的结果。

样例2

输入

1 3 2 2 3 1

输出

2 3 1 3 1 2

提示

• 1 <= nums.length <= 5 × 10⁴
• 0 <= nums[i] <= 5000
• 题目数据保证，对于给定的输入 nums，总能产生满足题目要求的结果。

进阶

• 你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？