UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2094. [Poi2010]Ones

Statistics 下载数据

Description

说有一个01串,去掉前导0和结尾0,那么现在有一头一尾两个1对不对……
如果一个1,它处于开头或者结尾,且不与1相邻,那么就称之为ufo……
10001010有两个ufo……10000000000011000000有一个ufo……10000001000000有两个ufo……00000100000000000只有一个ufo
sks(n) = 1..n这n个数的二进制表示中ufo的总个数。
sks(5) = 5, sks(256) = 249
现在REP(n)表示把相同的叠在一起……啥意思呢……就是
REP(111111000001100) = {6, 5, 2, 2}
代表一开始有6个1,5个0,2个1,2个0。
现在给你REP(n),要你求REP(sks(n))。
|REP(n)| <= 10^6, n <= 2 ^ (10 ^ 9)

Input

输入:第一行一个整数n(1<=n<=1000,000),第二行n个由空格隔开的整数xi(1<=xi的总和<=1000,000,000)用题目开头说过的方法描述了一个二进制数这个二进制数表示的整数,这个整数大于0,小于2的1000,000,000此方。

Output

输出:第一行一个整数,为描述的二进制数的数字个数,第二行用题目开头的方法输出(用空格隔开),表示这个二进制数。

Sample Input

6
1 1 1 1 1 1

Sample Output

5
1 1 2 1 1

Hint

Source