A binary tree of building-floor sensor ids is given in level-order form (a single line of space-separated tokens, null marking a missing child; every non-null node contributes exactly two following tokens for its children). The tree always has at least one node.

Define a node's height as the number of edges on the longest path from that node down to a leaf in its subtree (a leaf has height 0). The tree is height-balanced if, for every node in the tree, the heights of its left and right subtrees differ by at most 1 (treat a missing child as height -1, so that a leaf has height 0).

Formally: define height(missing child) = -1, and height(node) = 1 + max(height(left), height(right)). The tree is balanced if, at every node, |height(left) - height(right)| <= 1 (again using -1 for a missing child).

If the tree is height-balanced, print its overall height (height(root)). Otherwise, print -1.

Input format

Line 1: space-separated level-order tokens describing the binary tree (integers and the token null). The tree has at least 1 node.

Output format

A single integer: the tree's height if it is height-balanced, otherwise -1.

Constraints

• 1 <= number of nodes <= 500
• Each node value is an integer with -1000 <= value <= 1000

1 2 3 4

2

1 2 null 3 null null null 4

-1