Salem and Sticks

1000ms

262144K

Description:

Salem gave you $$$n$$$ sticks with integer positive lengths $$$a_1, a_2, \ldots, a_n$$$.

For every stick, you can change its length to any other positive integer length (that is, either shrink or stretch it). The cost of changing the stick's length from $$$a$$$ to $$$b$$$ is $$$|a - b|$$$, where $$$|x|$$$ means the absolute value of $$$x$$$.

A stick length $$$a_i$$$ is called almost good for some integer $$$t$$$ if $$$|a_i - t| \le 1$$$.

Salem asks you to change the lengths of some sticks (possibly all or none), such that all sticks' lengths are almost good for some positive integer $$$t$$$ and the total cost of changing is minimum possible. The value of $$$t$$$ is not fixed in advance and you can choose it as any positive integer.

As an answer, print the value of $$$t$$$ and the minimum cost. If there are multiple optimal choices for $$$t$$$, print any of them.

Input:

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of sticks.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 100$$$) — the lengths of the sticks.

Output:

Print the value of $$$t$$$ and the minimum possible cost. If there are multiple optimal choices for $$$t$$$, print any of them.

Sample Input:

3
10 1 4

Sample Output:

3 7

Sample Input:

5
1 1 2 2 3

Sample Output:

2 0

Note:

In the first example, we can change $$$1$$$ into $$$2$$$ and $$$10$$$ into $$$4$$$ with cost $$$|1 - 2| + |10 - 4| = 1 + 6 = 7$$$ and the resulting lengths $$$[2, 4, 4]$$$ are almost good for $$$t = 3$$$.

In the second example, the sticks lengths are already almost good for $$$t = 2$$$, so we don't have to do anything.

Informação

Provedor Codeforces

Código CF1105A