Consider augmenting each node v in a higher level with the number of missing entries in the gap from v to the next node over.