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