409184: GYM103451 D Krosh and powers of two

Krosh calls positive integer interesting if it can be represented as a sum of two powers of number two, in other words $$$x$$$ is interesting if there exists two non-negative numbers $$$i \ge 0$$$, $$$j \ge 0$$$, $$$i \neq j$$$ such that $$$x = 2^i + 2^j$$$. Krosh has big number $$$m$$$ in binary number system. Length of this number does not exceed $$$2*10^5$$$. Help Krosh to calculate how many interesting numbers there are from $$$1$$$ to $$$m$$$.

In first line you are given number $$$1 \le n \le 2 * 10^5$$$ the length of the number. In second line there is number $$$m$$$ of $$$n$$$ digits in binary system. Every digit is $$$0$$$ or $$$1$$$ and first digit is $$$1$$$.

4
1010

5

2
11

1