给定一个长度为 $( n )$ 的整数序列，请你使用快速排序算法对该序列进行从小到大的排序。

在本题中，要求你采用 Hoare 分区方案 完成快速排序。

输入格式

第一行输入一个正整数 $( n )$，表示序列长度。 第二行输入 $( n )$ 个整数 $( a_1, a_2, \dots, a_n )$。

输出格式

输出一行，包含排序后的 $( n )$ 个整数，相邻元素之间用一个空格隔开。

数据范围

• $( 1 \le n \le 10^5 )$
• $( -10^9 \le a_i \le 10^9 )$

样例 1

5
4 2 5 1 3

1 2 3 4 5

样例 2

6
10 -3 7 7 2 0

-3 0 2 7 7 10