Let p[0], p[1], ..., p[N1] be a permutation of integers between 0 and N1, inclusive. A binary search tree is a rooted binary tree with an integer value stored at each node. We use the following pseudocode to construct a binary search tree from the permutation p:
Create the root and put p[0] there
For each i in (1, 2, ..., N1)
Call insert(root, p[i])
Procedure insert(vertex V, integer X)
If X < number at V
If V has left child
Call insert(left child of V, X)
Else
Create new left child of V with value X
Else
If V has right child
Call insert(right child of V, X)
Else
Create new right child of V with value X
End
End
You are given three ints: N, seed and limit. Use the following pseudocode to generate the permutation p (be sure to use 64bit integers in computations where needed; note that '/' represents integer division and % represents remainder):
X := seed
For each i in (0, 1, ..., N1)
p[i] := i
X := (X * 295397169) % 1073741789;
If (X * 1000000) / 1073741789 < limit
X := (X * 295397169) % 1073741789
// generate j within [0, i]
j := (X * (i + 1)) / 1073741789
// j <= i, so p[j] is already initialized
swap(p[i], p[j])
End
End
John constructed a binary search tree from the generated permutation using the pseudocode described above.
Return the sum of the heights of all nodes in the constructed tree. The height of a node V is the number of nodes in the path from the root to V.
