Fight for the throne P74274

Statement

A country is currently kingless. To choose a new king, $n$ warriors, numbered $1 \dots n$ , will fight as follows: First, 1 arrives and sits on the throne. Afterwards, $2 \dots 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, \dots, w_n$ . You can assume $1 \le n \le 10^5$ , $w_1 = 1$ , and that, for each $2 \le i \le 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++