題目描述

有N堆寶藏一字排開，每堆寶藏的重量都十分重，所以只能夠借助起重機搬運，每次可以移動任意重量的寶藏，但只能移到相鄰的寶藏上，例如第X堆只能把寶藏移到第X-1堆或第X+1堆上，而邊上的只能有一種移法。

現在需要找出要令每堆寶藏重量都一樣時，最少要移動多少次。

為了方便計算，寶藏的總重量必定是N的倍數。

輸入格式

第一行只有一個整數N ( 1 <= N <= 100 )
第二行有N個整數A₁, A₂, ..., A_N ( 1 <= A_i <= 10000 )

輸出格式

一個整數，代表最少要移動的次數。

Samples

["3\r\n1 1 7","7\r\n1 3 1 9 1 5 1"]

["2","5"]

提示

輸入樣例一： ( 1, 1, 7 )
1. 把第3堆移4到第1堆 ( 1, 5, 3 )
2. 把第2堆移2到第1堆 ( 3, 3, 3 )
所以需要2次。

輸入樣例二：( 1, 3, 1, 9, 1, 5, 1 )
1. 把第4堆移4到第3堆 ( 1, 3, 5, 5, 1, 5, 1 )
2. 把第3堆移2到第2堆 ( 1, 5, 3, 5, 1, 5, 1 )
3. 把第2堆移2到第1堆 ( 3, 3, 3, 5, 1, 5, 1 )
4. 把第4堆移2到第5堆 ( 3, 3, 3, 3, 3, 5, 1 )
5. 把第6堆移2到第7堆 ( 3, 3, 3, 3, 3, 3, 3 )
所以需要5次。

原始資料

• Zero1 題號：a662
• Hydro 題號：Z0662
• Locale：zh_TW
• Display：practice