Збалансуй-но!#4150
Лідеру команди "Відбій" на День Народження подарували підвішене бінарне дерево. Проте, йому не сподобалось, що дерево було незбалансованим. Тепер він хоче видалити мінімальну кількість вершин у дереві, щоб воно стало збалансованим. Перед тим, як видалити вершину з дерева, він зобов'язаний видалити усі вершини з її піддерева.
Нагадаємо, що дерево є збалансованим тоді і лише тоді, коли висота його лівого і правого піддерев відрізняється не більше ніж на (висота порожнього дерева дорівнює нулю, а висота дерева з однієї вершини — одиниці). Коренем дерева є вершина .
У першому рядку вхідного файлу задано ціле число — кількість вершин у дереві (1 \leq n \leq 1111). У наступних рядках задано по два цілих числа left_i та right_i — номери лівого та правого сина вершини відповідно, або , якщо цього сина не існує.
У єдиному рядку вихідного файлу виведіть одне число — шукану мінімальну кількість вершин, що видаляються.
Приклад 1