排队

第一届喵喵喵编程大赛即将开始，本次比赛有 $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$ 种可能，下面分别列出： |分组情况|最终排列 $q$| |:-:|:-:| |$(2)(1)(4)(3)$|$1,2,3,4$| |$(2)(1)(4,3)$|$1,2,3,4$| |$(2)(1,4)(3)$|$1,4,2,3$| |$(2)(1,4,3)$|$1,3,4,2$| |$(2,1)(4)(3)$|$1,2,3,4$| |$(2,1)(4,3)$|$1,2,3,4$| |$(2,1,4)(3)$|$1,2,4,3$| |$(2,1,4,3)$|$1,2,3,4$| 关于表格，我们以 $(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$ 的一个排列。 |子任务编号|$n\le$|特殊性质|分值| |:-:|:-:|:-:|:-:| |1|$3$||11| |2|$16$||16| |3|$2000$||22| |4|$3\times 10^5$|A|17| |5|$3\times 10^5$||34| - 特殊性质 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$ 的情形。