题目描述

第一届喵喵喵编程大赛即将开始，本次比赛有 $n$ 只喵喵参赛，编号依次为 $1,2,\ldots, n$，已经分成了若干组，每一组喵喵的编号都是连续的一段。

根据报名情况，你已经知道第 $i$ 只喵喵会第 $p_i$ 个到达现场，保证 $p_i$ 构成 $1\sim n$ 的排列。

一组喵喵的到达时间被定义为这一组喵喵中最早到达的喵喵的到达时间。

喵喵的排队规则如下：

• 先把所有的喵喵组按每组喵喵的到达时间从小到大排序。
• 然后对于同一组喵喵，按照每只喵喵的到达时间从小到大排序。

按照这个排队规则，可以得到一个新的排列 $q_1,\ldots,q_n$，其中 $q_i$ 表示从前往后第 $i$ 只喵喵的到达时间。

你已经知道了所有 $p_i$，但是不清楚喵喵的分组，你想知道排列 $q_1,q_2,\ldots,q_n$ 的字典序最大可能是什么。

输入格式

输入的第一行有一个正整数 $n$，表示喵喵数量。

第二行有 $n$ 个正整数 $p_1,p_2,\ldots,p_n$，表示每只喵喵的到达顺序。

输出格式

输出一行 $n$ 个正整数，表示 $q$ 的字典序最大可能。

4
2 1 4 3

1 4 2 3

6
6 5 4 3 2 1

1 2 3 4 5 6

提示

【样例 1 解释】

所有可能的分组情况有 $8$ 种可能，下面分别列出：

关于表格，我们以 $(2)(1,4,3)$ 这个分组方式为例，演示排队结果的计算：

• 首先 $(2)$ 这组喵喵的到达时间为第 $2$，$(1,4,3)$ 这组喵喵的到达时间为第 $1$，从而 $(1,4,3)$ 排在前面。
• 然后 $(1,4,3)$ 这组喵喵内部按照到达时间排序，得到 $1,3,4$；$(2)$ 这组喵喵内部按照到达时间排序得到 $2$。
• 最后把每组喵喵的排序结果拼起来，得到 $1,3,4,2$。

【样例 2 解释】

读者不难验证，无论喵喵怎么分组，因为无论组内还是组外都是从小到大排序的，所以 $q_i$ 永远是 $1,2,3,4,5,6$。

【数据范围】

对于全体数据，保证 $1\le n\le 3\times 10^5$，且 $p_i$ 构成 $1\sim n$ 的一个排列。

• 特殊性质 A：存在 $1\le k\le n$ 使得 $p_1>p_2>\ldots >p_{k-1}> p_k < p_{k+1}<\ldots < p_n$。例如，样例 2 就是 $k=6$ 的情形。