Девочка Маша гуляла в лесу и нашла полное бинарное дерево высоты \(n\) и перестановку \(p\) длины \(m=2^n\).
Полное бинарное дерево высоты \(n\) — это такое корневое дерево, что каждая вершина кроме листьев имеет ровно двух сыновей, а длина пути от корня до любого из листьев равна \(n\). Ниже на картинке изображено полное бинарное дерево для \(n=2\).
Перестановкой называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\). Например, [\(2,3,1,5,4\)] является перестановкой, а [\(1,2,2\)] не является (\(2\) встречается дважды), и [\(1,3,4\)] тоже не является перестановкой (\(n=3\), но в массиве есть \(4\)).
Пронумеруем \(m\) листьев этого дерева слева направо. В листе с номером \(i\) записано значение \(p_i\) (\(1 \le i \le m\)).
Например, если \(n = 2\), \(p = [3, 1, 4, 2]\), дерево будет выглядеть так:
Маша считает дерево красивым, если значения в его листьях упорядочены слева направо по возрастанию.
За одну операцию Маша может выбрать произвольную не являющуюся листом вершину дерева и поменять местами ее левого и правого сына (вместе с их поддеревьями).
Например, если Маша применит эту операцию к корню рассмотренного выше дерева, оно приобретет следующий вид:
Помогите Маше понять, сможет ли она за некоторое количество операций сделать дерево красивым. Если сможет, то выведите минимальное количество операций, чтобы сделать дерево красивым.
Примечание
Рассмотрим первый тест.
В первом наборе входных данных можно действовать так (фиолетовым цветом выделена вершина, к которой на текущем шаге применяется операция):
Можно показать, что нельзя сделать дерево красивым за меньшее число операций.
Во втором наборе входных данных можно показать, что нельзя сделать дерево красивым.
В третьем наборе входных данных дерево сразу является красивым.