Description

给定 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ​, 求它们两两相乘再相加的和，即 $S=a_1a_2 + a_1a_3 + \cdots, a_1a_n + a_2a_3 + \cdots + a_{n-2}a_{n-1} + a_{n - 2}a_{n}+a_{n-1}a_{n}$

Input Format

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$

Output Format

输出一个整数 $S$，表示所求的和。请使用合适的数据类型进行运算。

4
1 3 6 9​

117​

Hint

对于 30%的数据, $1≤n≤1000,1≤a_i≤100$

对于所有评测用例, $1≤n≤2×10^5,1≤a_i≤1000$

Source

前缀和