#ABC405C. 乘积之和

乘积之和

AT_abc405_c [ABC405C] Sum of Product

题目描述

\hspace{15pt}给定一个数列 a=(a1,a2,…,an)a=(a_1,a_2,\dots,a_n),求

∑1≦i<j≦naiaj\sum\limits_{1 \leqq i < j \leqq n} a_i a_j

的值。

输入格式

\hspace{15pt}第一行输入一个整数 n(2≦n≦3×105)n \left(2 \leqq n \leqq 3 \times 10^5\right) 代表数列的长度。

\hspace{15pt}第二行输入 nn 个整数 $a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^4\right)$ 代表数列中的元素。

输出格式

\hspace{15pt}在一行上输出一个整数,代表答案。

\hspace{15pt}由于答案可能很大(最大约为 4.5×10184.5 \times 10^{18}),请使用 6464 位整数存储结果。

测试样例

3
4 2 3
26

样例 1 解释

\hspace{15pt}答案为 $\sum\limits_{1 \leqq i < j \leqq n} a_i a_j = a_1a_2+a_1a_3+a_2a_3 = 4 \times 2+4 \times 3+2 \times 3 = 26$。

2
9 45
405
10
7781 8803 8630 9065 8831 9182 8593 7660 7548 8617
3227530139