Background

With NOIP 2014 approaching, the JC Academy Informatics Club is actively preparing. So usqwedf, Liang Dada, Xumuban Zhuanchang, YH dashen, and LHT dashen also plan to launch the “Lanxiang Cup.”

In the library, MC and others successively hosted the JC Academy joint contests “Qiliaobei” and “UID#3.” It is said that YH dashen is also painstakingly studying network flow. Hearing this, WZF shenniu and MZC shenniu from JC Academy Grade 13 Class 13 decided to co-create the “Shisandian Cup.” But making a full problem set is hard work, so they decided to rope in SY, a fellow classmate and club member who was in the library searching for the “Hello World” standard solution.

Poor juruo SY had tons of homework and refused to agree. Finally, WZF shenniu compromised: “I’ll give you one problem. If you solve it, we won’t make you write problems; otherwise… you know.” SY had barely finished reading the problem WZF improvised when he said, almost in tears, “You win.”

But juruo SY was really too weak to write problems, so he racked his brains and came up with an idea—just copy the problem WZF gave.

Problem Description

There are $n$ bookshelves in a circle. The shelf behind shelf $1$ is shelf $2$, the shelf behind shelf $2$ is shelf $3$, …, the shelf behind shelf $n-1$ is shelf $n$, and the shelf behind shelf $n$ is shelf $1$. Shelf $i$ has $b_i$ books. To make the library look nicer, WZF shenniu asks SY to move books so that every shelf ends up with the same number of books. Because the total number of moved books might be large, SY is only allowed to move books from a shelf to its two adjacent shelves. What is the minimum number of books SY needs to move?

Input Format

There are $2$ lines. The first line contains a positive integer $n$. The second line contains $n$ non-negative integers, where the $i$-th is $b_i$.

Output Format

Output $n+1$ lines.

The first line contains a positive integer $m$, the minimum total number of books SY needs to move.

Then output $n$ lines. In the $i$-th line, output two integers $af_i$ and $ab_i$, meaning SY moves $af_i$ books and $ab_i$ books from shelf $i$ to the shelf in front of it and the shelf behind it, respectively.

5
15 7 11 3 14

12
2 3
-3 0
0 1
-1 -6
6 -2

Hint

Constraints and Notes

For all testdata, $1 \le n \le 10^5 + 1$, and $n$ is odd; $b_i \le 10^7$.

If $af_i$ is negative, it means SY moves $-af_i$ books from the shelf in front of shelf $i$ onto shelf $i$.

Similarly, if $ab_i$ is negative, it means SY moves $-ab_i$ books from the shelf behind shelf $i$ onto shelf $i$.

Translated by ChatGPT 5