C - Sum of Product Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

\displaystyle \sum_{1\leq i< j\leq N} A_iA_j の値を求めてください。

制約

  • 2\leq N \leq 3\times 10^5
  • 1\leq A_i \leq 10^4
  • 入力は全て整数

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

3
4 2 3

出力例 1

26

\displaystyle \sum_{1\leq i< j\leq N} A_iA_j=A_1A_2+A_1A_3+A_2A_3=4\cdot 2+4\cdot 3+2\cdot 3=26 です。

入力例 2

2
9 45

出力例 2

405

入力例 3

10
7781 8803 8630 9065 8831 9182 8593 7660 7548 8617

出力例 3

3227530139

Score : 300 points

Problem Statement

You are given a length-N integer sequence A = (A_1, A_2, \dots, A_N).

Compute the value of \displaystyle \sum_{1\leq i< j\leq N} A_iA_j.

Constraints

  • 2 \le N \le 3 \times 10^5
  • 1 \le A_i \le 10^4
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Output the answer.

Sample Input 1

3
4 2 3

Sample Output 1

26

We have \displaystyle \sum_{1\leq i< j\leq N} A_iA_j=A_1A_2+A_1A_3+A_2A_3=4\cdot 2+4\cdot 3+2\cdot 3=26.

Sample Input 2

2
9 45

Sample Output 2

405

Sample Input 3

10
7781 8803 8630 9065 8831 9182 8593 7660 7548 8617

Sample Output 3

3227530139