{"problem":{"name":"101 to 010","description":{"content":"$N$ cells are arranged in a row. Some of them may contain tokens. You are given a string $s$ that consists of `0`s and `1`s. If the $i$\\-th character of $s$ is `1`, the $i$\\-th cell (from left) contai","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"code_festival_2017_qualb_d"},"statements":[{"statement_type":"Markdown","content":"$N$ cells are arranged in a row. Some of them may contain tokens. You are given a string $s$ that consists of `0`s and `1`s. If the $i$\\-th character of $s$ is `1`, the $i$\\-th cell (from left) contains a token. Otherwise, it doesn't contain a token.\nSnuke wants to perform the following operation as many times as possible. In each operation, he chooses three consecutive cells. Let's call the cells $X, Y, Z$ from left to right. In order for the operation to be valid, both $X$ and $Z$ must contain tokens and $Y$ must not contain a token. Then, he removes these two tokens and puts a new token on $Y$.\nHow many operations can he perform if he performs operations in the optimal way?\n\n## Constraints\n\n*   $1 \\leq N \\leq 500,000$\n*   $|s| = N$\n*   Each character in $s$ is either `0` or `1`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$s$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"code_festival_2017_qualb_d","tags":[],"sample_group":[["7\n1010101","2\n\nFor example, he can perform two operations in the following way:\n\n*   Perform an operation on the last three cells. Now the string that represents tokens becomes `1010010`.\n*   Perform an operation on the first three cells. Now the string that represents tokens becomes `0100010`.\n\nNote that the choice of operations matters. For example, if he chooses three cells in the middle first, he can perform no more operations."],["50\n10101000010011011110001001111110000101010111100110","10"]],"created_at":"2026-03-03 11:01:14"}}