While Melman sat in a narrow box and floated somewhere, he was very bored. To entertain himself, he started playing a game with n coins he found in a drawer.

He put the coins in front of him in a row and numbered them from 1 to n from left to right. Some coins are heads up, and some are tails up. Then, Melman starts making moves. First, he counts the number k - the number of coins that are heads up. If there are no such coins, then the game ends. Otherwise, he makes a move - flips the coin number k.

Help Melman determine how many times he will have to make a move to finish the game by the initial position of the coins. Or tell that the game will continue indefinitely.

Input

The first line contains one integer n (1 ≤ n ≤ 105) - the number of coins. The next line contains a string of n characters "0" and "1" - the initial location of the coins. The symbol "0" corresponds to a coin lying tails up, and the symbol "1" to heads up.

Output

If the game will last forever, print "-1". Otherwise, print the number of moves Melman has to make before the game ends.