题目描述

Let $x$ be a sequence of zeros and ones.

An utterly forlorn one (UFO) in $x$ 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 $x_2$ 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(460\ 288)=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\le k\le 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_1,x_2,\cdots,x_k$ ($0<x_i\le 1\ 000\ 000\ 000$), separated by single spaces.

The sequence $x_1,x_2,\cdots,x_k$ forms the succinct representation of the number $n$.

You may assume that $x_1+x_2+\cdots+x_k\le 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_1,y_2,\cdots,y_l$, separated by single spaces.

The sequence $y_1,y_2,\cdots,y_l$ is to form the succinct representation of $sks(n)$.

题目大意

设 $x$ 是一个由 $\texttt{01}$ 组成的序列。一个 UFO 指的是序列中第一个 $1$ 或者最后一个 $1$ 且不和任何一个 $1$ 相邻。例如 $\texttt{10001010}$ 有两个 UFO，$\texttt{1101011000}$ 没有 UFO，$\texttt{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(n)$，求 $REP(sks(n))$。

输入格式:

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

输出格式:

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

6
1 1 1 1 1 1

5
1 1 2 1 1