AtCoder Beginner Contest 043

C - いっしょ / Be Together


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 200

問題文

N 個の整数 a_1,a_2,..,a_N が与えられます。えび君はこれらを書き換えて全て同じ整数にしようとしています。各a_i (1≦i≦N)は高々一回しか書き換えられません(書き換えなくても良い)。整数xを整数yに書き換えるとき、コストが(x-y)^2かかります。仮にa_i=a_j (i≠j)だとしても、ひとつ分のコストで同時に書き換えることは出来ません(入出力例2 を参照)。えび君が目的を達成するのに必要なコストの総和の最小値を求めてください。

制約

  • 1≦N≦100
  • -100≦a_i≦100

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 ... a_N

出力

えび君が全てを同じ整数に書き換えるのに必要なコストの総和の最小値を出力せよ。


入力例 1

2
4 8

出力例 1

8

全てを6に書き換えると、コストの総和は(4-6)^2+(8-6)^2=8となり、これが最小です。


入力例 2

3
1 1 3

出力例 2

3

全てを2に書き換えると(1-2)^2+(1-2)^2+(3-2)^2=3となります。各a_iごとに書き換えるので、二つの1を一度にコスト(1-2)^2で書き換えられるわけではないことに注意してください。


入力例 3

3
4 2 5

出力例 3

5

4は書き換えずに、25を共に4に書き換えることで(2-4)^2+(5-4)^2=5が達成できて、これが最小です。


入力例 4

4
-100 -100 -100 -100

出力例 4

0

何も書き換えなくともえび君は目的を達成しています。よってこの場合コストは0です。

Score : 200 points

Problem Statement

Evi has N integers a_1,a_2,..,a_N. His objective is to have N equal integers by transforming some of them.

He may transform each integer at most once. Transforming an integer x into another integer y costs him (x-y)^2 dollars. Even if a_i=a_j (i≠j), he has to pay the cost separately for transforming each of them (See Sample 2).

Find the minimum total cost to achieve his objective.

Constraints

  • 1≦N≦100
  • -100≦a_i≦100

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the minimum total cost to achieve Evi's objective.


Sample Input 1

2
4 8

Sample Output 1

8

Transforming the both into 6s will cost (4-6)^2+(8-6)^2=8 dollars, which is the minimum.


Sample Input 2

3
1 1 3

Sample Output 2

3

Transforming the all into 2s will cost (1-2)^2+(1-2)^2+(3-2)^2=3 dollars. Note that Evi has to pay (1-2)^2 dollar separately for transforming each of the two 1s.


Sample Input 3

3
4 2 5

Sample Output 3

5

Leaving the 4 as it is and transforming the 2 and the 5 into 4s will achieve the total cost of (2-4)^2+(5-4)^2=5 dollars, which is the minimum.


Sample Input 4

4
-100 -100 -100 -100

Sample Output 4

0

Without transforming anything, Evi's objective is already achieved. Thus, the necessary cost is 0.


Submit提出する