题目描述

译自 POI 2010 Stage 3. Day 2「Ones」

设 $x$ 是一个由 $01$ 组成的序列。一个 UFO 指的是序列中第一个 $1$ 或者最后一个 $1$ 且不和任何一个 $1$ 相邻。例如 $10001010$ 有两个 UFO，$1101011000$ 没有 UFO，$1000$ 只有一个 UFO。

设 $1$ 到 $n$ 的数的二进制表示中 UFO 的总数为 $sks(n)$。例如，$sks(5) = 5$, $sks(64) = 59$, $sks(128) = 122$, $sks(256) = 249$。

我们需要处理非常大的数字。因此 $n$ 会用压缩的形式表示。设 $x$ 是一个正整数，$x_2$ 是其二进制表示（最高位为 $1$），则该数的压缩形式 $REP(x)$ 为一个序列，表示连续相同数位的数量。例如：

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

已知 $REP(n)$，求 $REP(sks(n))$。

输入格式

第一行有一个整数 $k$ ，表示一个正整数 $n$ 的压缩形式。 接下来一行有 $k$ 个整数 $x_1$, $x_2$, ..., $x_k$ ，用空格分隔，表示 $n$ 的压缩形式序列。保证 $x_1 + x_2 + ... + x_k \le 1000000000$，也就是说 $0 < n < 2^{1000000000}$。

输出格式

输出两行，第一行有一个正整数 $l$，第二行有 $l$ 个正整数 $y_1$, $y_2$, ..., $y_l$，用空格分隔，表示 $sks(n)$ 的压缩形式。

样例

输入

6
1 1 1 1 1 1

输出

5
1 1 2 1 1

序列 $1,1,1,1,1,1$ 为 $101010_2 = 42$ 的压缩形式，$sks(42) = 45$，而 $45 = 101101_2$ 的压缩形式为 $1,1,2,1,1$。

数据范围与提示

对于 $100\%$ 的数据， $1 \le k \le 1000000$ , $0 < x_i \le 1000000000$ 。

Translated by vincent163