A museum's rooms form a binary tree. A camera installed in a room monitors that room, its parent room, and its direct child rooms. Determine the minimum number of cameras needed so that every room is monitored by at least one camera.
Input format
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is an integer room id or null for a missing child. Children of null nodes are omitted. (Ids do not affect the answer.)
Output format
A single integer: the minimum number of cameras.
Constraints
- The tree has between 1 and 500 nodes (the root is always present).
- Each room id is between -1000000 and 1000000.