Монокарп планирует провести соревнование по смешанным единоборствам. В нем будет три весовых категории: легкий вес, средний вес и тяжелый вес. Победитель в каждой категории определяется по системе плей-офф.
В частности, это подразумевает, что количество участников в каждой категории должно быть степенью двойки. Дополнительно в каждой категории должно быть ненулевое количество участников.
\(n\) участников уже зарегистрировались на соревнование, \(i\)-й из них весит \(a_i\). Чтобы разделить участников на категории, Монокарп планирует установить две целых границы весов \(x\) и \(y\) (\(x < y\)).
Все участники с весом строго меньше \(x\) будут считаться легким весов. Все участники с весом больше или равно \(y\), будут считаться тяжелым весом. Все остальные участники будут считаться средним весом.
Возможно, что распределение не сделает количество участников в каждой категории степенью двойки. Оно так же может сделать и пустые категории. Чтобы решить эти проблемы, Монокарп может пригласить любое количество участников в каждую категории.
Обратите внимание, что Монокарп не может выгнать никого из \(n\) участников, которые уже зарегистрировались на соревнование.
Однако, он хочет пригласить как можно меньше дополнительных участников. Помогите Монокарпу выбрать \(x\) и \(y\) таким образом, чтобы суммарное количество необходимых дополнительных участников было как можно меньше. Выведите это количество.
Выходные данные
На каждый набор входных данных выведите одно целое число — наименьшее количество дополнительных участников, которых Монокарпу необходимо пригласить после того, как он выберет границы весов \(x\) и \(y\).
Примечание
В первом наборе входных данных Монокарп может выбрать \(x=2\) и \(y=3\). Легкая, средняя и тяжелая весовые категории будут содержать \(2\), \(1\) и \(1\) участников, соответственно. Они все являются степенями двойки, поэтому дополнительных участников не нужно.
Во втором наборе входных данных вне зависимости от выбора \(x\) и \(y\) в одной категории будет \(1\) участник, в остальных — \(0\). Монокарпу придется пригласить \(1\) участника в обе из оставшихся категорий.
В третьем наборе входных данных Монокарп может выбрать \(x=1\) и \(y=2\). Легкая, средняя и тяжелая весовые категории будут содержать \(0\), \(3\) и \(3\) участников, соответственно. В каждую категорию придется пригласить по одному участнику.
В четвертом наборе входных данных Монокарп может выбрать \(x=8\) и \(y=9\). Легкая, средняя и тяжелая весовые категории будут содержать \(8\), \(0\) и \(0\) участников, соответственно. В среднюю и тяжелую категории придется пригласить по одному участнику.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
3 1 2 1
1
1
6
2 2 2 1 1 1
8
6 3 6 3 6 3 6 6
|
0
2
3
2
|