Дано число в двоичной системе счисления, состоящее из \(n\) битов, возможно, с лидирующими нулями. Например, для \(n = 5\) число \(6\) задается как \(00110\), а для \(n = 4\) число \(9\) задается как \(1001\).
Фиксируем некоторое целое \(i\), такое что \(1 \le i \le n\). За одну операцию вы можете поменять местами любые два соседних элемента битовой записи. Ваша цель — найти наименьшее количество операций, за которое можно превратить исходное число в делящееся на \(2^i\), или сказать, что это невозможно.
Обратите внимание, что для каждого \(1 \le i \le n\) вы решаете задачу независимо.
Выходные данные
В каждом наборе входных данных для каждого \(1 \le i \le n\) выведите наименьшее количество операций, необходимое для того, чтобы сделать число делящимся на \(2^i\), или выведите \(-1\), если это нельзя сделать.
Примечание
В первом наборе входных данных мы не можем менять элементы местами, и число \(1\) не делится на \(2\).
Во втором наборе входных данных исходное число равно \(1\). Оно не делится на \(2\), но если применить операцию, то получится число, в двоичной записи равное \(10\), что в десятичной системе равно \(2\), а значит, делится на \(2\). Но на \(4\) это число не делится, а с помощью операции нельзя получить других чисел.
В третьем наборе входных данных исходное число равно \(2\). Для \(i = 1\) операции применять не нужно, так как исходное число делится на \(2\). Для \(i = 2\) можно применить одну операцию, поменяв первые два бита местами (в двоичном представлении получим число \(100\), которое задает число \(4\)). Для \(i = 3\) ответа не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
1
2
01
3
010
5
10101
7
0000111
12
001011000110
|
-1
1 -1
0 1 -1
1 3 -1 -1 -1
3 6 9 12 -1 -1 -1
0 2 4 6 10 15 20 -1 -1 -1 -1 -1
|