C - Squared Error Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

長さ N の数列 A が与えられます。
各要素同士の差の 2 乗の和、すなわち \displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2 を求めてください。

制約

  • 2 \le N \le 3 \times 10^5
  • |A_i| \le 200
  • 入力に含まれる値は全て整数

入力

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

N
A_1 A_2 A_3 \cdots A_N

出力

答えを出力せよ。

入力例 1

3
2 8 4

出力例 1

56

\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2 = (8 - 2)^2 + (4 - 2) ^ 2 + (4 - 8) ^ 2 = 56 です。

入力例 2

5
-5 8 9 -4 -3

出力例 2

950

Score : 300 points

Problem Statement

Given is a number sequence A of length N.
Find the sum of squared differences of every pair of elements: \displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2.

Constraints

  • 2 \le N \le 3 \times 10^5
  • |A_i| \le 200
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 A_3 \cdots A_N

Output

Print the answer.

Sample Input 1

3
2 8 4

Sample Output 1

56

We have \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2 = (8 - 2)^2 + (4 - 2) ^ 2 + (4 - 8) ^ 2 = 56.

Sample Input 2

5
-5 8 9 -4 -3

Sample Output 2

950