Maximizing the Lexicographical Queue of Meow Groups

The First Meow Meow Meow Programming Contest is about to start! There are \(n\) cats (numbered \(1,2,\dots,n\)) participating, and they have been arbitrarily partitioned into groups. In each group the cats’ IDs form a contiguous segment. You are given a permutation \(p_1,p_2,\dots,p_n\) meaning that the \(i\)th cat will arrive the \(p_i\)th. (The \(p_i\) form a permutation of \(1,2,\dots,n\).)

For any group, its arrival time is defined as the smallest arrival time among the cats in the group. Once the groups are determined the queue is formed in two steps:

1. Sort all the groups in increasing order of their arrival time (i.e. by the minimum \(p\) value in each group).
2. Within each group, arrange the cats in increasing order of their individual arrival time.

This yields a new permutation \(q_1,q_2,\dots,q_n\) where \(q_i\) is the arrival time of the \(i\)th cat in the queue.

You know \(p_1, p_2, \dots, p_n\), but the grouping is unknown. Your task is to choose a valid grouping (i.e. a partition of the indices \(1\) to \(n\) into contiguous segments) so that the resulting \(q\) is lexicographically maximum.

More formally, let a valid grouping be a partition of \(\{1,2,\dots,n\}\) into contiguous segments. For each segment \(S\) let its sorted order (in increasing order) be \(s_1,s_2,\dots,s_k\) where \(s_1=\min_{i\in S}p_i\). Then, after sorting all segments by \(s_1\) (in increasing order) and concatenating them, you obtain the permutation \(q\). Among all valid groupings, output the lexicographically maximum \(q\); that is, if \(q=(q_1,q_2,\dots, q_n)\) and \(q'=(q'_1,q'_2,\dots,q'_n)\) are two results then \(q\) is larger than \(q'\) if for some index \(j\) we have \(q_1=q'_1,\dots,q_{j-1}=q'_{j-1}\) and \(q_j>q'_j\).

Note on formulas: All formulas are written in LaTeX format (e.g. \(n\), \(p_i\), \(q\), etc.).

inputFormat

The first line contains a single integer \(n\) \( (1\le n\le 10^5)\) indicating the number of cats. The second line contains \(n\) space‐separated integers \(p_1,p_2,\dots,p_n\) which form a permutation of \(\{1,2,\dots,n\}\).

outputFormat

Output one line containing \(n\) space‐separated integers: the lexicographically maximum \(q_1,q_2,\dots,q_n\) obtainable by choosing a valid grouping.

sample

3
2 3 1

1 3 2