Сбалансируй-ка!
Лидеру команды "Отбой" на День Рождения подарили подвешенное бинарное дерево. Однако, ему не понравилось, что дерево было несбалансировано. Теперь он хочет удалить минимальное количество вершин в дереве, чтобы оно стало сбалансированным. Перед тем, как удалить вершину из дерева, он обязан удалить все вершины из её поддерева.
Напомним, что дерево является сбалансированным тогда и только тогда, когда высота его левого и правого поддеревьев отличается на 1 (высота пустого равна нулю, а высота дерева из одной вершины - единице). Корнем дерева является вершина 1.
Входные данные
В первой строке входного файла задано целое число n - количество вершин в дереве (1 ≤ n ≤ 1111). В следующих n строках заданы по два целых числа left_i и right_i - номера левого и правого ребёнка вершины соответственно, или 0, если этого ребёнка не существует.
Выходные данные
В единственной строке выходного файла выведите одно число - искомое минимальное количество удаляемых вершин.