Maze Exploration (APCS 2022-10 Advanced)

Ming is exploring a tree-shaped maze. The maze consists of several chambers, and each chamber has a positive integer number. A chamber with an even number has two possible exits to chambers in the next layer, left and right. A chamber with an odd number has three possible exits to chambers in the next layer, left, middle, and right. However, an exit may also be a dead end and not lead to any other chamber.

Ming starts from the starting chamber and visits the next-layer chambers through the left, middle, and right exits in order when applicable. Whenever he reaches a chamber, he recursively explores all chambers below it in the same way, and finally returns to that chamber. After all exits of the starting chamber have been explored, the maze exploration ends. During exploration, for each chamber, Ming records its number the first time he enters it. If an exit of a chamber is a dead end, he records one zero. Given Ming's record, compute the sum of the absolute differences of the numbers of all connected pairs of chambers in the maze.

For example, consider the tree-shaped maze below. Rectangles are odd-numbered chambers and ovals are even-numbered chambers. Chamber \(5\) is the starting chamber, and each solid dot labeled \(0\) indicates that the corresponding exit is a dead end.

Ming recursively explores all chambers below chamber \(2\), then all chambers below chamber \(8\), and finally all chambers below chamber \(1\) before returning to the starting chamber. The exploration record is "\(5\) \(2\) \(10\) \(0\) \(0\) \(0\) \(8\) \(0\) \(0\) \(1\) \(7\) \(0\) \(0\) \(0\) \(0\) \(6\) \(0\) \(0\)".

The connected pairs of chambers in this example are \((5, 2)\), \((5, 8)\), \((5, 1)\), \((2, 10)\), \((1, 7)\), and \((1, 6)\), six pairs in total. The required sum is \(|5 - 2| + |5 - 8| + |5 - 1| + |2 - 10| + |1 - 7| + |1 - 6| = 29\).

Input

The input contains one line of nonnegative integers: Ming's record. Adjacent numbers are separated by one space. The number of chambers is at most \(10^5\). The number of each chamber is distinct, positive, and at most \(10^5\). The deepest layer of the chambers is at most \(40\).

Output

Output one integer: the sum of the absolute differences of the numbers of all connected pairs of chambers. The answer may exceed \(2^{31}\).

The chamber structure of sample 1 is shown below:

Sample Input 1

2 6 0 8 14 0 0 0 10 0 4 0 0

Sample Output 1

26

Sample Input 2

5 2 10 0 0 0 8 0 0 1 7 0 0 0 0 6 0 0

Sample Output 2

29

Sample Explanation 2

This is the example described in the statement.

Scoring

Each test case has a time limit of \(1\) second, and Python programs have a time limit of \(2\) seconds. Scores are based on the number of test cases passed. Let \(n\) be the number of chambers:

• Subtask 1, 20 points: \(n \le 20\), all chamber numbers are positive even numbers, all exits of the starting chamber lead to another chamber, and every other chamber has at most one exit leading to another chamber. See sample 1.
• Subtask 2, 20 points: \(n \le 10^3\).
• Subtask 3, 60 points: no additional constraints.

Source

Official APCS advanced sample booklet, October 2022 programming task.