Problem : 56 - 狡兔三窟

Problem Statistics

Solved Member: 32　　Submission: 180　　User Tried: 37

Statement:

俗話說狡兔有三窟。洞穴是很好用的東西，除了避天敵之外，也是彰顯兔子社會地位的手段。

HH是一隻大兔子，他並不是普通的兔子，而是隻好威好威的國王兔子。他建造了N($3 \leq N \leq 1000000$)個洞穴來當他的地下宮殿。
HH的洞穴頗有玄機，首先，他每個洞穴的大小不一定相等，可以給不同的動物進來遊玩。另外，他的洞穴是一張完全圖，也就是任2點之間一定有獨立的通道相連。也就是整張圖有$\LARGE \frac{N(N-1)}{2}$條通道。

你是他皇宮的侍衛，每天要替HH檢查洞穴的安全性以避免他被綁架。你發現，每個洞穴的危險性與洞穴的大小成正比，比方說小的洞穴可能只有蛇闖進來，而大一點的洞穴卻能夠跑進一隻老虎！所我們可以對每條由i連到j的通道定義他的危險程度：

$W_{ij} = N_i \times N_j$，其中$N_i , N_j$分別代表第i點以及第j點的洞口大小。整座宮殿的危險度就是所有通道危險度的總和。

身為一位盡責的侍衛，整座宮殿的洞穴大小你都瞭若指掌，你現在需要能夠快速又準確的求出整座宮殿的危險程度。

Input:Output:

第1行有1個整數N，代表點的個數。
接下來有N個整數($0 \leq N_i \leq 10000$)，代表每個洞穴的大小。

其中30%的測資滿足 $3 \leq N \leq 1000$。

輸出1行數字，代表整座宮殿的危險性。
由於答案很大，你只需要輸出除以2^64的餘數就可以了。

Sample Input:Sample Output:

3
1 2 3

HINT:

注意記憶體。

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	1000kb
1	1000ms	1000kb	10
2	1000ms	1000kb	10
3	1000ms	1000kb	10
4	2500ms	1000kb	10
5	2500ms	1000kb	10
6	2500ms	1000kb	10
7	2500ms	1000kb	10
8	2500ms	1000kb	10
9	2500ms	1000kb	10
10	2500ms	1000kb	10