Fight for the throne P74274


Statement
 

pdf   zip

thehtml

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 wi be the number of the warrior on the throne at time i. Knowing the numbers wi, 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 w1, …, wn. You can assume 1 ≤ n ≤ 105, w1 = 1, and that, for each 2 ≤ i ≤ n, wi is either i or wi−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++