A country is currently kingless. To choose a new king, n warriors, numbered 1 … n, will fight as follows: First, 1 arrives and sits on the throne. Afterwards, 2 … n arrive in order to challenge the current champion. Every time, the winner of the fight sits on the throne, and the loser escapes. At the end, the champion on the throne is declared the king.

Now, let us assume that each warrior has a different strength between 1 and n,
and that the outcome of each fight
is only determined by the relative strengths of both fighters.
Let w_{i} be the number of the warrior on the throne at time i.
Knowing the numbers w_{i},
can you bound the minimum and the maximum possible strength of each warrior?

Input

Input consists of several cases,
each one with n
followed by w_{1}, …, w_{n}.
You can assume 1 ≤ n ≤ 10^{5},
w_{1} = 1,
and that, for each 2 ≤ i ≤ n,
w_{i} is either i or w_{i−1}.

Output

For every case, print n + 1 lines: For every warrior i, print the interval of his possible strength, or just his strength if you can decide it for sure. Finally, print a line with 10 dashes.

Public test cases

**Input**

4 1 2 3 4 3 1 1 1 8 1 1 3 4 4 4 7 7

**Output**

1: 1 2: 2 3: 3 4: 4 ---------- 1: 3 2: [1, 2] 3: [1, 2] ---------- 1: [2, 5] 2: [1, 4] 3: [3, 6] 4: [6, 7] 5: [1, 6] 6: [1, 6] 7: 8 8: [1, 7] ----------

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++