Problem Statement

Consider a tree of N vertices, labeled 1 through N in some arbitrary order. A path connecting vertex X and vertex Y (with X < Y) qualifies as an ideal path whenever every other vertex lying along that path has a label strictly between X and Y. You're given an array A = [A 1 , A 2 , ..., A N ] encoding the tree's structure. For each valid i (1 <= i <= N), whenever A i != 0, there's an edge joining vertex i and vertex A i . Exactly one entry equals 0, marking the tree's root. When the same value shows up at two different indices, that value is the shared parent of both. As an example , take N = 7 and A = {0,5,5,1,4,1,4}. Here's how each index maps under A: i 1 2 3 4 5 6 7 A[i] 0 5 5 1 4 1 4 A[1] = 0 tells us vertex 1 is the root. A[2] and A[3] both equal 5, so vertex 5 parents vertices 2 and 3. A[4] and A[6] both equal 1, so vertex 1 parents vertices 4 and 6. A[5] and A[7] both equal 4, so vertex 4 parents vertices 5 and 7. Putting these edges together produces this tree: (Diagr