TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

81.0% (17/21)

Submission's AC Ratio

37.4% (43/115)

Tags

Description

最近胖胖國小又要舉辦園遊會了。

每年胖胖國小都會全校總動員,一起做一件有趣的事來做為園遊會的精神象徵與主題。

例如: 大胃王接力賽呀、環島接力馬拉松呀...,總之都會需要全校總動員才能夠達成。

今年胖胖國小則決定一起疊一個很大很大的羅漢,來做為這次活動的精神錦標。

現在全校的師生都已經站成一排了,為了平衡的關係,所以每個人頂多只被一個人踩。

不過為了防止跌倒,又為了防止最下面那層的人被壓死,所以可以扶著旁邊的欄杆。

因此對於某個人來說,除了受踩他的那個人的重量影響以外,不受更上層的人重量影響

為什麼會指受踩他的那個人影響呢?因為假如你被一個比你胖的人踩,你當然會覺得很不爽囉XD!

因此A踩B,則A體重一定小於B。

不過事情還沒解決,因為這個隊伍實在是太長了,所以要重新整頓非常困難。

因此每個人的右腳只可能踩位置在他右邊的人,左腳只能踩位置在他左邊的人。

當然踩人不一定要踩兩個,只踩一個也是OK的。

而且假如某個人兩隻腳踩的人疊的高度不一樣也沒關係,因為最後他們都可以在地上墊東西以達成平衡。

不過為了減少隊伍動到,所以有一個規定是說:

當A原本在B左邊,且B現在在A上方時,B原本右邊的人,A都不能踩

同樣的當A原本在B左邊,且A現在在B上方時,A原本左邊的人,B都不能踩

當然對於每一種採法都會有穩定與不穩定的事情發生。

因此穩定度的估算是: 所有踩與被踩的人的體重差的平方和

現在給你這n個人的體重(假設全部都不相同),問你說最穩定的穩定度為何?

Input Format

輸入一數n(1<=n<=2000000)。
接下來有n個整數,每個數皆不超過int儲存範圍。

Output Format

輸出一數代表最小穩定度的大小。

Sample Input 1

9
2 4 3 1 6 7 8 5 9

Sample Output 1

38

Hints

範例測資解釋:
總之堆積起來的圖會長這樣

因此最小穩定度是(2-1)2 + (3-2)2 + (4-3)2 + (5-1)2 + (6-5)2 + (7-6)2 + (8-7)2 + (9-5)2 = 38

※2009/7/23 補充題目敘述(by math120908): 感謝su_horng。

Problem Source

原TIOJ1549 / Problem Setter: math120908

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 6000 65536 262144 1
1 6000 65536 262144 2
2 6000 65536 262144 3
3 6000 65536 262144 4
4 6000 65536 262144 5