Coco the Monkey lives on an island, numbered 1.
An explorer is going on a voyage over N days. On day 1, he stays on the island Coco the Monkey is at. On day 2, he discovers island 2. On day 3, he discovers island 3. On day i, he discovers island i.
For each island that he discovers, he opens up a sea route that connects the newly discovered island to one island that has already been discovered. All sea routes are of equal length. Initially, only the island Coco the Monkey lives on is considered discovered.
On each day, Coco the Monkey wonders, what is the longest distance between two discovered islands? Answer Coco the Monkey's queries!
The first line of input will contain one integer, N.
The next N - 1 lines of input will contain one integer each, the island that the newly discovered island is connected to by a sea route.
Output N - 1 lines. On the ith line, output the longest possible distance between any two discovered islands on day (i+1).
Subtask 1 (36%): 2 ≤ N ≤ 1000.
Subtask 2 (64%): 2 ≤ N ≤ 200 000.
Subtask 3 (0%): Sample Testcases
Sample Testcase 1