534. Coin Distribution

0

Medium

Given a binary tree with n nodes and a total of n coins, determine the minimum number of moves required to distribute the coins evenly among all nodes. In each move, you can choose two adjacent nodes and transfer one coin from one node to the other.

Input Format

Enter the value of each node, followed by a Boolean indicating whether the node has a left child. If it does, enter the left child's value. The input follows a recursive pattern, where the left child's children are processed before moving to the parent's right child.

Output Format

Output the number of moves required to distribute the coins evenly among all nodes.

Example

Input

3 true 0 false false true 0 false false

Output

2

Constraints

None

Loading...

View Submissions

Console