Есть ребро-взвешенное полное двоичное дерево с $$$n$$$ листьями. Полное двоичное дерево определяется как дерево, в котором каждая нелистовая вершина имеет ровно 2 дочерних вершины. Для каждой нелистовой вершины обозначим одного из ее детей как левого ребенка, а другого — как правого.

Это двоичное дерево обладает очень странным свойством. Для каждой нелистовой вершины одно из ребер к ее детям имеет вес $$$0$$$, а другое ребро — вес $$$1$$$. Обратите внимание, что ребро с весом $$$0$$$ может идти как к левому ребенку, так и к правому.

Вы забыли, как выглядит дерево, но, к счастью, вы помните некоторую информацию о листьях в виде массива $$$a$$$ длины $$$n$$$. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$, $$$a_i$$$ представляет собой расстояние$$$^\dagger$$$ от корня до $$$i$$$-го листа (в порядке обхода dfs$$$^\ddagger$$$). Определите, существует ли полное двоичное дерево, удовлетворяющее массиву $$$a$$$. Обратите внимание, что восстанавливать дерево не нужно.

$$$^\dagger$$$ Расстояние от вершины $$$u$$$ до вершины $$$v$$$ определяется как сумма весов ребер на пути от вершины $$$u$$$ до вершины $$$v$$$.

$$$^\ddagger$$$ Порядок листьев в dfs определяется вызовом следующей функции $$$\texttt{dfs}$$$ на корне бинарного дерева.

dfs_order = [] — порядок обхода dfs

функция dfs(v):
    если v — лист:
        добавить v в конец dfs_order
    иначе:
        dfs(левый ребенок v)
        dfs(правый ребенок v)

dfs(корень)