8199번 - Ones 다국어

Let x be a sequence of zeros and ones. An utterly forlorn one (UFO) in  is the extreme (either first or last) one that additionally does not neighbour with any other one. For instance, the sequence 10001010 has two UFOs, while the sequence 1101011000 has no UFO, and the sequence 1000 has only one UFO.

Let us denote the total number of UFOs in the binary representations of the numbers from 1 to n with sks(n). For example, sks(5)=5, sks(64)=59, sks(128)=122, sks(256)=249.

We will be working with very large numbers. Therefore, we shall represent them in a succinct way. Suppose x is a positive integer and x2 is its binary representation (starting with 1). Then the succinct representation of x is the sequence REP(x) consisting of positive integers denoting the lengths of successive blocks of the same digits. For example:

REP(460288)=REP(1110000011000000000_2)=(3,5,2,9)

REP(408)=REP(110011000_2)=(2,2,2,3)

Your task is to write a program that finds the sequence REP(sks(n)) given REP(n).

The first line of the standard input holds one integer k (1 ≤ k ≤ 1,000,000) denoting the length of the succinct representation of a positive integer n. The second line of the standard input holds k integers x₁,x₂,…,x_k, (0 < x_i ≤ 1,000,000,000), separated by single spaces. The sequence x₁,x₂,…,x_k forms the succinct representation of the number n. You may assume that x₁+x₂+…+x_k ≤ 1,000,000,000, i.e., 0 < n < 2^{1,000,000,000}.

Your program is to print out two lines to the standard output. The first one should contain a single positive integer l. The second line should hold l positive integers y₁,y₂,…,y_l, separated by single spaces. The sequence y₁,y₂,…,y_l is to form the succinct representation of sks(n).

The sequence 1,1,1,1,1,1 forms the succinct representation of 101010₂=42, sks(42)=45, while 45=101101₂ is succinctly represented by 1,1,2,1,1.