TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

You are given an array A of n integers. You have to find another array B
such that the array C (ci=ai+bi, for a<=i<=n) is:


  • Strictly increasing,

  • s=|b1|+|b2|+...+|bn| is minimized.

Warn: 本題有 specialjudge

Input Format

The first line of the input contains an integer T, indicates the number of test cases.


Each test case consists of two lines.
The first line contains an integer n (1<=n<=a5000).
The second line contains n space-separated integers, each from the interval [-109, 109].

Output Format

For each test case please output two lines. To the first line write a single number s, where s = |b1|+|b2|+...+|bn|. To the second line write n space-separated integers representing the elements of the array B. If there are multiple solutions, output any of them.

Sample Input 1

1
4
1 1 1 1

Sample Output 1

4
-1 0 1 2

Hints

Problem Source

Migrated from old NTUJ.

MIT Individual 2009

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 524288 400