409184: GYM103451 D Krosh and powers of two

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Krosh and powers of twotime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$$$.

Input

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$$$.

ExamplesInput
4
1010
Output
5
Input
2
11
Output
1

加入题单

上一题 下一题 算法标签: