A magical string s consists of only '1' and '2' and obeys the following rules:


	The string s is magical because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string s itself.


The first few elements of s is s = "1221121221221121122……". If we group the consecutive 1's and 2's in s, it will be "1 22 11 2 1 22 1 22 11 2 11 22 ......" and the occurrences of 1's or 2's in each group are "1 2 2 1 1 2 1 2 2 1 2 2 ......". You can see that the occurrence sequence is s itself.

Given an integer n, return the number of 1's in the first n number in the magical string s.

&nbsp;
Example 1:

Input: n = 6
Output: 3
Explanation: The first 6 elements of magical string s is "122112" and it contains three 1's, so return 3.


Example 2:

Input: n = 1
Output: 1


&nbsp;
Constraints:


	1 &lt;= n &lt;= 105


class Solution:
    def magicalString(self, n: int) -> int:
        queue, ans, i = deque([2]), 1, 1

        while i <= n - 2:
            m = queue.popleft()
            ans += (m == 1)
            queue.extend([1 + (i % 2 == 0)] * m)
            i += 1

        return ans
class Solution {
    public int magicalString(int n) {
        if(n <= 3)
            return 1;
        Magical m = new Magical();
        int ans = 1;
        for(int i = 3; i < n; ++i)
            if(m.next() == 1)
                ++ans;
        return ans;
    }
}

class Magical{

    private Deque<Integer> nums;
    private int n;

    public Magical(){
        nums = new ArrayDeque<>();
        nums.offerLast(1);
        nums.offerLast(1);
        n = 1;
    }

    public int next(){
        if(n-- < 0){
            int c = nums.pollFirst();
            n = c - 2;
            int curr = 3 - nums.peekLast();
            for(; c > 0; --c)
                nums.offerLast(curr);
            return curr;
        }
        return nums.peekLast();
    }
}
class Solution {
public:
    int magicalString(int n) {
        string s="122";
        int sz=3;
        int start=2,lastDig=2;
        while(sz<n){
            int cnt=s[start++]-'0';
            int currDig=(lastDig==2)?1:2;
            for(int i=0;i<cnt;i++){
                s.push_back('0'+currDig);
                sz++;
            }
            lastDig=currDig;
        }
        int ans=0;
        for(int i=0;i<n;i++){
            if(s[i]=='1'){
                ans++;
            }
        }
        return ans;
    }
};
var magicalString = function(n) {
    const stack = ['1', '2', '2'];
    let magic = 2;

    while (stack.length < n) {
        const count = stack[magic++];
        const last = stack[stack.length - 1];
        const addStr = last === '1' ? '2' : '1';

        for (let n = 1; n <= count; n++) stack.push(addStr);
    }
    return stack.slice(0, n).filter(str => str === '1').length;
};
Magical String