高さを統一する
コスト削減を目指して、市の設計部門はすべての建物の高さを同じにそろえるよう依頼してきました。建物が一律の高さになれば、建設コストを大幅に抑えられると考えられています。
市内には
n 棟の建物があり、それぞれの高さは と異なります。建物の高さを x だけ変更すると、x 分の会議が必要です。あなたは多忙なため、この会議に使う時間をできるだけ少なく抑えたいと考えています。会議に費やす時間を最小限にするには、どのようにすればよいでしょうか？Input
最初の行には、整数
n (1 ≤ n ≤ ) が 1 つ与えられます。次の行には、空白区切りの
n 個の整数 (1 ≤ ≤ ) が与えられ、これは建物の初期の高さを表します。Output
会議に費やす最小の合計時間を示す整数を 1 つ出力してください。
Examples
Input | Output |
5
1 4 8 2 9 | 14 |
Explanation
最適な高さは 4 です。たとえば、1 から 4 に変更するには 3 分、2 から 4 に変更するには 2 分、8 から 4 に変更するには 4 分、9 から 4 に変更するには 5 分かかり、合計すると 14 分となります。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB