A magical string s consists only of the numerical characters $'1'$ and $'2'$ and satisfies a unique self-generating property: grouping consecutive identical characters produces a sequence of group lengths that equals the string s itself.

The first few digits of the magical string s begin as follows:
s = $"1221121221221121122..."$

Grouping the consecutive identical digits in s gives:
$"1"$, $"22"$, $"11"$, $"2"$, $"1"$, $"22"$, $"1"$, $"22"$, $"11"$, $"2"$, $"11"$, $"22"$, $...$

The lengths of these consecutive groups are:
$1$, $2$, $2$, $1$, $1$, $2$, $1$, $2$, $2$, $1$, $2$, $2$, $...$

Notice that the sequence formed by the group lengths is identical to the magical string s itself.

Given an integer n, return the number of times the character $'1'$ appears in the first n characters of the magical string s.

Constraints:

• $1 \leq `n` \leq 10^5$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.