Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Physical Education and Buns

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe Physical education teacher at SESC is a sort of mathematician too. His most favorite topic in mathematics is progressions. That is why the teacher wants the students lined up in non-decreasing height form an arithmetic progression.

To achieve the goal, the gym teacher ordered a lot of magical buns from the dining room. The magic buns come in two types: when a student eats one magic bun of the first type, his height increases by one, when the student eats one magical bun of the second type, his height decreases by one. The physical education teacher, as expected, cares about the health of his students, so he does not want them to eat a lot of buns. More precisely, he wants the maximum number of buns eaten by some student to be minimum.

Help the teacher, get the maximum number of buns that some pupils will have to eat to achieve the goal of the teacher. Also, get one of the possible ways for achieving the objective, namely, the height of the lowest student in the end and the step of the resulting progression.

Input

The single line contains integer *n* (2 ≤ *n* ≤ 10^{3}) — the number of students. The second line contains *n* space-separated integers — the heights of all students. The height of one student is an integer which absolute value doesn't exceed 10^{4}.

Output

In the first line print the maximum number of buns eaten by some student to achieve the teacher's aim. In the second line, print two space-separated integers — the height of the lowest student in the end and the step of the progression. Please, pay attention that the step should be non-negative.

If there are multiple possible answers, you can print any of them.

Examples

Input

5

-3 -4 -2 -3 3

Output

2

-3 1

Input

5

2 -3 -1 -4 3

Output

1

-4 2

Note

Lets look at the first sample. We can proceed in the following manner:

- don't feed the 1-st student, his height will stay equal to -3;
- give two buns of the first type to the 2-nd student, his height become equal to -2;
- give two buns of the first type to the 3-rd student, his height become equal to 0;
- give two buns of the first type to the 4-th student, his height become equal to -1;
- give two buns of the second type to the 5-th student, his height become equal to 1.

To sum it up, when the students line up in non-decreasing height it will be an arithmetic progression: -3, -2, -1, 0, 1. The height of the lowest student is equal to -3, the step of the progression is equal to 1. The maximum number of buns eaten by one student is equal to 2.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 11:51:05 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|