Restore Rating Changes

Bytie was preparing for the PA contest and recorded a sequence of n numbers on paper. The k-th number (for 1 ≤ k ≤ n) represents the maximum total rating increase obtained in any contiguous block of exactly k contests. In other words, if the unknown rating change sequence is x₁, x₂, ..., x_m (with m ≥ n), and we denote by

\( S(j,k)=x_j+x_{j+1}+\cdots+x_{j+k-1} \quad (1 \le j \le m-k+1) \)

then the numbers written on paper satisfy:

\( a_k = \max_{1 \le j \le m-k+1} S(j,k) \) for every k = 1,2,...,n.

Your task is to restore any rating change sequence (i.e. a sequence of integers, which can be negative) of length at least n that is consistent with the given data.

Note: It is guaranteed that the input data is consistent so that a valid rating change sequence exists.

Hint: One way to solve this problem is to choose a sequence such that the prefix of the first n elements exactly yields the given values, and then append several very negative numbers to ensure that no other contiguous block produces a sum larger than the prefix block. For example, if you let

\( b_1=a_1, \quad b_i=a_i-a_{i-1} \text{ for } i=2,3,\ldots,n, \quad \text{and} \quad c_j=-T \text{ for some large } T,\ j=1,2,\ldots,n-1,\)

then the sequence

\( x = [b_1, b_2, \ldots, b_n, c_1, c_2, \ldots, c_{n-1}] \)

will work provided that T is sufficiently large (for example, T = 10⁹).

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of values written on paper.

The second line contains n space‐separated integers: a₁, a₂, ... , a_n, where a_k is the maximum total rating increase over any contiguous block of exactly k contests.

outputFormat

On the first line, output a single integer m (m ≥ n), the length of your rating change sequence.

On the second line, output m space‐separated integers representing the rating change sequence.

sample

1
5

1
5

</p>