UFO Counting and Succinct Representation

Consider a binary string (x) (a sequence of 0’s and 1’s) representing a positive integer (with no extra leading zeroes). An utterly forlorn one (UFO) in (x) is defined as the extreme 1 – that is, the first occurrence of 1 or the last occurrence of 1 – provided that it does not have a neighbouring 1. (Note that if there is only one 1 then it is counted only once.) For example, in the binary string 10001010 the leftmost 1 (at position 1) and the rightmost 1 (at position 7) are UFO’s so the UFO–count is 2; in 1101011000 there is no UFO; and in 1000 the unique 1 is a UFO.

Define (sks(n)) as the total number of UFO’s in the binary representations of all numbers from (1) to (n). For instance, (sks(5)=5), (sks(64)=59), (sks(128)=122) and (sks(256)=249).

Since (n) (and hence (sks(n))) may be very large, we represent a positive integer (x) in a succinct way. If (x_2) is the binary representation of (x) (which always begins with a 1), then the succinct representation (REP(x)) is defined as the sequence of positive integers giving the lengths of successive blocks of identical digits. For example, [ REP(460288)=REP(1110000011000000000_2)=(3,5,2,9)] [ REP(408)=REP(110011000_2)=(2,2,2,3)]

Your task is: Given (REP(n)) (that is, the succinct representation of (n)), compute and output (REP(sks(n))) — the succinct representation of (sks(n)).

Input format

The input is given as a sequence of positive integers. The first integer \(k\) indicates the number of entries in \(REP(n)\); the next \(k\) positive integers are the entries. (Note that the binary representation of \(n\) begins with a 1, so the first block always corresponds to 1’s.)

Output format

Output the succinct representation of \(sks(n)\) as a sequence of positive integers in the format (a,b,c,...) (without spaces around commas).

Explanation

For example, if the input is 3\n1 1 1 then \(REP(n)=(1,1,1)\) so \(n\) (in binary) is 101 (i.e. \(n=5\)). We have \(sks(5)=5\) and \(REP(5)=(1,1,1)\). Another example: if the input is 2\n1 6 then \(REP(n)=(1,6)\) means \(n_2=1\,0^6\) i.e. 1000000 (which is 64 in decimal) and \(sks(64)=59\). Since \(59_2=111011\), its succinct representation is (3,1,2).

Notes

• Your program must be efficient enough to handle very large \(n\) (given in succinct form).
• You are advised to think in terms of counting by binary length and performing digit DP on the binary representation, without explicitly enumerating all numbers up to \(n\).

inputFormat

The first line contains a single integer (k) ((k \ge 1)), which is the number of entries in the succinct representation (REP(n)). The second line contains (k) space‐separated positive integers. For example, an input might be:

3 1 1 1

outputFormat

Output a single line containing the succinct representation of (sks(n)) in the format: (a,b,c,...) with no extra spaces.

sample

3
1 1 1

(1,1,1)