题目描述

给你一个 $1 \sim n$ 的排列 $p_1 \ldots p_n$，你需要对排列进行一次操作，使得这个排列的字典序最大。

操作的方式为选择区间 $[l,r]$，反转 $p_l \ldots p_r$ 的元素，然后交换 $p_1 \ldots p_{l-1}$ 和 $p_{r+1} \ldots p_n$ 的元素（交换的可能为空区间）

例如, 对排列 $5,3,2,1,4$ 进行 $[2,3]$ 的区间操作之后得到的结果为 $1,4,2,3,5$ ( 反转 $(3,2)$ 为 $(2,3)$ ) 再交换 $(5)$ 和 $(1,4)$ 的位置。

输入格式

输入第一行包含一个整数 $n$

之后一行包含 $n$ 个由 $1\sim n$ 组成且互不相同的整数。表示排列 $p_1 \ldots p_n$

输出格式

输出一行包含 $n$ 个整数表示完成操作之后字典序最大的序列。

样例数据

5
2 3 1 5 4

5 4 1 3 2

大样例

P1486.in / P1486.out

数据范围和提示

• 对于 $30\%$ 的数据, $n \lt 20$
• 对于 $50\%$ 的数据，$n \lt 400$
• 对于$70\%$ 的数据， $n \lt 3000$
• 对于$100\%$ 的数据， $n \lt 3\times 10^5$