Background
Winter solstice approaches, days are short and nights are long. The river is cold and dark, yet the eastern clouds are pink. Outside the window, a flock of gulls wakes from slumber; inside, the room is filled with fragrance as the morning meal is prepared.
Morning study and evening toil hasten one's drowsiness. In the quiet of the night, one reads by the lamp, finding rest only when the wick burns out. Please take on this heavy burden for me, so that we may dance freely and celebrate this birthday in harmony.
Description
K is currently studying ancient poetry and prose. The writing style of ancient texts does not always follow modern conventions; sometimes this is due to the unique grammatical structures of the language, and other times it is for subjective reasons such as parallel structure or rhythmic harmony. However, annotating the correct reading order directly next to the original text is not only aesthetically unpleasing in terms of layout, but also cumbersome to find the next index. To facilitate reading, K has designed a set of auxiliary markers to indicate the order, replacing the need for direct numbering.
There are three types of auxiliary markers: adjacent inversion markers, adjacent sequence markers, and remote jump markers. The two types of adjacent markers define the relative reading order between two adjacent characters, so they must appear between two adjacent characters and cannot appear at the beginning or end of a sentence. The remote jump marker, when used alone, only acts on the preceding character, so it must appear after a single character; it can appear at the end of a sentence but not at the beginning.
The adjacent inversion marker * is used to indicate that, in the correct reading order, the last character before the marker should immediately follow the first character after the marker. For example, the correct reading order of "研表*究明，汉字序*顺并不定*一影阅*响读" is "研究表明，汉字顺序并不一定影响阅读". Adjacent inversion markers can be used consecutively, indicating that the corresponding entire segment of text should be read one by one from back to front. For example, the normal order of "林暗草惊风，将军夜引弓" is "林暗风惊草，将军夜引弓", so it can be marked as "林暗草*惊*风" to indicate the swapping of the subject and object.
For more complex reading orders, remote jump markers can be used to assist understanding. For example, in "马之千里者，一食或尽粟一石", "一石" is a quantity phrase modifying "粟", so in the normal reading order, it should be "一食或尽一石粟". To annotate such non-adjacent order swaps, a remote jump marker can be used to point out a group of characters that need to be read from back to front; such a group is called a remote jump structure. To prevent confusion, it is stipulated that for any two remote jump structures, either all characters of one group are before any character of the other, or all characters of one group are located between two consecutive characters of the other; it is not allowed for the characters of two remote jump structures to cross each other in the original string. Because multiple levels of nesting may occur, the remote jump marker has the form p-q, where the positive integer p represents the number of nested levels, and q represents the order within that group. If a remote jump structure does not contain any other nested remote jump structures, the level p of each marker in that group is $1$; otherwise, it is the maximum level of all nested remote jump structures $+1$. For the same remote jump structure, the characters are numbered q $=1, 2, 3, \cdots$ from back to front based on their appearance in the original string, which is also the actual reading order. When reading text with auxiliary markers, if a character is followed by a remote jump marker with index q $\ge 2$, that character should be temporarily skipped; until a remote jump marker with q exactly equal to $1$ is encountered, at which point one should read the single characters before the markers p-1, p-2, etc., of the same group from back to front, until a remote jump marker with a larger p, another remote jump marker with the same p-1 (at which point this marker should mark another remote jump structure), or the beginning of the text is encountered.
For the example sentence from "Ma Shuo" mentioned above, the corresponding annotation method is "一食或尽粟1-2一石1-1". Another example, "入则无法家拂士，出则无敌国外患者，国恒亡，然后知生于忧患而死于安乐也", contains two instances of post-positioned adverbials ("然后知于忧患生而于安乐死也"), and the annotation method satisfying the requirements is "然后知生1-2于忧患1-1而死1-2于安乐1-1也". Additionally, the index q of remote jump markers in the same group must appear in descending order; that is, situations like p-2 p-3 p-1 are not allowed.
Since both adjacent inversion markers and remote jump markers can be used to indicate jumps opposite to the normal reading direction, it is stipulated that when one needs to read the preceding character immediately after reading a character, one must use the adjacent inversion marker. This rule creates a problem: when adjacent characters in the original text appear in the same remote jump structure, if these adjacent characters are not at the beginning or end of the remote jump structure, using the adjacent inversion marker to annotate this pile of characters might lead to ambiguity in the reading order. Fortunately, the solution is not complicated: simply split one remote jump structure into two or more at the position where the adjacent characters appear. Note that when splitting, the level corresponding to each new structure should be calculated independently.
When using remote jump markers, by default, only the reading order of the single character before the marker is changed. If the reading order of multiple consecutive characters needs to be pushed back, the adjacent sequence marker # should be used in conjunction, indicating that the first character after the marker should immediately follow the last character before the marker. For example, in "今日大风寒，寒风摧树木，严霜结庭兰", the positions of the subject "庭兰" and the object "严霜" are swapped, so it can be annotated as "严1-3#霜结1-2庭兰1-1". For the sake of brevity, it is required that the adjacent sequence marker must be used in conjunction with a remote jump marker with index q $\ge 2$, but multiple adjacent sequence markers can be used consecutively according to actual needs; in this case, the remote jump marker is annotated only before the first adjacent sequence marker. For example, the normal order of "七八个星天外，两三点雨山前" is "天外七八个星，山前两三点雨", so it can be annotated as "七1-2#八#个#星天外1-1，两1-2#三#点#雨山前1-1".
When reading text annotated with auxiliary markers, the default is to process each character from front to back in the normal reading order. If a character has no auxiliary marker and its preceding character has no adjacent sequence marker, the character should be read directly; otherwise, the character is temporarily ignored. When encountering a character annotated with a remote jump marker with index $1$ (corresponding to ignoring the remote jump markers of the same group and any related adjacent sequence markers) or a character without an auxiliary marker (corresponding to ignoring at least one adjacent inversion marker), read this character first, then return to read the ignored characters according to the corresponding rules.
To prevent ambiguity when using markers, in addition to the above rules, it is also stipulated:
Between any two adjacent characters, either no auxiliary marker is used, or a single adjacent inversion marker, a single adjacent sequence marker, a single remote jump marker, a combination of one remote jump marker and one adjacent inversion marker, or a combination of one remote jump marker and one adjacent sequence marker is used. After the last character, there is either no auxiliary marker or a single remote jump marker.
If a combination of a remote jump marker and any type of adjacent marker is used between two adjacent characters, the remote jump marker should be placed before the adjacent marker. Specifically, if it is a combination of a remote jump marker and an adjacent inversion marker, the index
qof the remote jump marker must be $1$.For any three consecutive characters, it is not allowed to mix adjacent inversion markers and adjacent sequence markers (regardless of whether they are paired with remote jump markers), i.e., undefined annotation methods such as
.#.*.or.*.#.cannot appear, where.represents a single character that needs to be annotated. Similarly, it is not allowed for the preceding character to be annotated with an adjacent sequence marker while the following character is annotated with a remote jump marker (regardless of whether this remote jump marker is combined with any adjacent marker).
However, K found that this system cannot mark arbitrary permutations. For example, "绿垂风折笋，红绽雨肥梅" has the order "风折绿笋垂，雨肥红梅绽" in modern Chinese, and it cannot be represented by any combination of markers. Therefore, K wants to know, for a given reading order, whether there exists an annotation method using only the three types of markers mentioned above. If it exists, please help K find the unique annotation method that satisfies the conciseness requirements.
Input
The first line contains a positive integer $K$, representing the length of the original string to be annotated. It is guaranteed that $1 \le K \le 10^6$.
The second line contains $K$ positive integers $p_1, p_2, \cdots, p_K$, where $p_i$ represents the position of the $i$-th character of the original string in the correct reading order. It is guaranteed that $p_1, p_2, \cdots, p_K$ is a permutation of $1, 2, \cdots, K$.
Output
Output a string.
If a valid annotation method exists, output the unique annotation method that satisfies the requirements, using a single . to represent each character in the original string.
Otherwise, output -1, indicating that no valid annotation method exists.
Examples
Input 1
4
1 3 2 4Output 1
..*..Note 1
"微斯人，吾谁*与归？"
Input 2
9
3 4 1 2 8 9 5 6 7Output 2
.1-2#...1-1.1-2#....1-1Note 2
"故1-2#国神游1-1，多1-2#情应笑我1-1。"
Input 3
4
2 4 1 3Output 3
-1Note 3
The other three reading orders of length $4$ that cannot be represented are: - $2, 4, 3, 1$; - $3, 1, 4, 2$; - $3, 2, 4, 1$.
Input 4
7
7 1 2 6 5 3 4Output 4
.1-2...1-1*.1-2..1-1Input 5
8
1 2 8 6 3 5 4 7Output 5
...2-2.1-2..1-1*..2-1Input 6
8
2 1 3 8 7 5 4 6Output 6
.*...*.1-2.*..1-1Subtasks
For all data, it is guaranteed that $1 \le K \le 10^6$ and $p_1, \cdots, p_K$ is a permutation of $1, \cdots, K$.